力扣-最小覆盖子串

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;}
}