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