记录最小覆盖子串

1.暴力解法

（1）枚举输入字符串s的所有长度大于等于T的子串；

（2）逐个判断这些子串中，那些覆盖了字符串T的所有字符；

（3）在枚举的过程中，记录符合条件的，长度最短的那个子串

2.带自己备注的滑动窗口解法

class Solution {
    public String minWindow(String s, String t) {
int sLen=s.length();
int tLen=t.length();
if(sLen==0||tLen==0||sLen<tLen){
    return "";
}

char[] charArrayS=s.toCharArray();
char[] charArrayT=t.toCharArray();

int[] winFreq=new int[128];
int[] tFreq=new int [128];
for(int c:charArrayT){
    tFreq[c]++;
}

int distance=0;//滑动窗口中包含多少个T中的字符的总数
int minLen=sLen+1;
int begin=0;

int right=0;
int left=0;

while(right<sLen){

if(tFreq[charArrayS[right]]==0){//如果S中右边界的的字符在T中为0;就把区间向右移动
right++;
continue;//只有满足上面的条件这里就直接开始一个新的循环
}

//只有右边界的字符在T中是存在的并且滑动窗口winFerq的字符数是小于T中的，就可以给distance中++
if(winFreq[charArrayS[right]]<tFreq[charArrayS[right]]){
distance++;
}

winFreq[charArrayS[right]]++;//给窗口的各个字符数进行记录增加
right++;

while(distance==tLen){//这一层循环在内部，当相等之后，就说明已经够了，这下只需要优化来找最小的字符串
if(right-left<minLen){
    minLen=right-left;
    begin=left;
}

if(tFreq[charArrayS[left]]==0){//如果S中左边界的的字符在T中为0;就把区间向左移动,因为把无关紧要的字符删除可以寻找最小的字符
    left++;
    continue;//只有满足上面的条件这里就直接开始一个新的循环
}

//只有左边界的字符在T中是存在的并且滑动窗口的字符数是等于T中的，就可以给distance中--
if(winFreq[charArrayS[left]]==tFreq[charArrayS[left]]){//搞不懂，好像是由于上一次的下面对滑动窗口的值--后，导致了这里的左边界字符数相同，所以这里要对distance--，关键是这一句代码和下一句代码的顺序问题！
distance--;
}

winFreq[charArrayS[left]]--;//给窗口的各个字符数进行记录减少，这里如果对下一次造成了影响，就会distance--
left++;
}
}
if(minLen==sLen+1){
    return "";
}
return s.substring(begin,begin+minLen);
    }
    
}

侵删