力扣-最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

给定一个字符串s,和目标字符串t，需要找出s中包含t中所有字符且长度最小子串，输出这个子串

滑动窗口，初始时左右指针都指向s的第一个字符,对于每个遍历到的窗口，判断当前窗口是否包含了t中所需要的所有字符，不是的话就移动右指针，是的话就移动左指针。

怎么判断当前窗口是否包含了t中所需要的字符？

可以定义一个distance这样的int变量，当移动右指针后，如果此时右指针指向的字符在当前窗口中的个数严格小于t中所需要的个数，那么distance++。

在移动左指针前,如果此时左指针指向的字符在当前窗口中的个数等于t中所需要的个数，那么distance--。

distance等于t中所含字符数量时，就说明当前窗口是一个符合条件的子串

class Solution {
    public String minWindow(String s, String t) {
           int ans=1000000;
        String ansString="";
        int [] target=new int[200];
        int [] window=new int[200];

        int ansCount=0;
        for (int i = 0; i <t.length() ; i++) {
            target[t.charAt(i)]++;
            ansCount++;
        }

        int distance=0;
        for (int l=0,r=0; r <s.length() ; r++) {
            char x =s.charAt(r);

            if(window[x]<target[x]){
                distance++;
            }
            window[x]++;
            int f=0;
            while(distance==ansCount){
                f=1;
//                if(ans>r-l+1){
//                    ans =r-l+1;
//                    ansString=s.substring(l,r+1);
//                }
                if( window[s.charAt(l)]==target[s.charAt(l)]){
                    distance--;
                }
                window[s.charAt(l)]--;
                l++;
            }
            //出循环说明distance不满足anscount了

            if(f==1&&ans>r-l+2){
                f=0;
                ans =r-l+2;
                ansString=s.substring(l-1,r+1);
            }
        }
        return ansString;
    }
}