滑动窗口小结

滑动窗口可以用来优化一些暴力求解问题，将时间复杂度降低到线性。

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

思路

• 先扫描一遍T，把对应的字符及其出现的次数存到 HashMap 中。
• 然后开始遍历S，就把遍历到的字母对应的 HashMap 中的 value 减一，如果减1后仍大于等于0，cnt 自增1。
• 如果 cnt 等于T串长度时，开始循环，纪录一个字串并更新最小字串值。然后将子窗口的左边界向右移，如果某个移除掉的字母是T串中不可缺少的字母(hash表中对应value>0)，那么 cnt 自减1，表示此时T串并没有完全匹配。

string minWindow(string s, string t) {
        unordered_map<char,int> map;
        for(auto c:t) map[c]++;
        int len=t.size();
        string res;
        for(int i=0,j=0,cnt=0;i<s.size();i++){
            if(--map[s[i]]>=0) cnt++;
            while(cnt==len){
                if(res.empty()||res.size()>i-j+1) res=s.substr(j,i-j+1);
                if(++map[s[j++]]>0) cnt--;//移动左边界
            }
        }
        return res;
    }

进一步理解
本来我们是可以开两个哈希表，这里为了节省空间，将其合并，遍历S字符串的时候，哈希表中字符出现的次数可以理解还缺多少个，就可以满足和T字符串匹配。这样一来就能很好理解在移动左边界的判断条件++hash[s[j++]]>0 表示左边界指针移动之后，缺的个数大于0.

438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

滑动窗口 思路非常类似上一题76.最小覆盖子串

这个题目的滑动窗口大小固定，因此需要先调整大小，然后添加满足条件的答案。

vector<int> findAnagrams(string s, string p) {
       unordered_map<char,int> map;
       for(auto c:p) map[c]++;
       int total=p.size();
       vector<int> res;
       for(int i=0,j=0,cnt=0;j<s.size();j++){
           if(--map[s[j]]>=0) cnt++; //移动右指针
           //移动左指针 维护窗口大小为p.size
           while(j-i+1>total){
               if(++map[s[i++]]>0) cnt--;
           }
           if(cnt==total) res.push_back(i);
       }
       return res;

   }