滑动窗口问题

1. 最小覆盖子串

给定字符S、T，找出字符串S中包含T所有字母的最小子串。

滑动窗口算法的思路是这样：

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

基本框架代码：

   string s, t;
   // 在 s 中寻找 t 的「最小覆盖子串」
   int left = 0, right = 0;
   string res = s;
   
   while(right < s.size()) {
       window.add(s[right]);
       right++;
       // 如果符合要求，移动 left 缩小窗口
       while (window 符合要求) {
           // 如果这个窗口的子串更短，则更新 res
           res = minLen(res, window);
           window.remove(s[left]);
           left++;
       }
   }
   return res;

考虑如何判断window子串符合要求？

可以用两个哈希表当作计数器，用一个哈希表 needs 记录字符串 t 中包含的字符及出现次数，用另一个哈希表 window 记录当前「窗口」中包含的字符及出现的次数，如果 window 包含所有 needs 中的键，且这些键对应的值都大于等于 needs 中的值，那么就可以知道当前「窗口」符合要求了，可以开始移动 left 指针了。

   string minWindow(string s, string t) {
       // 记录最短子串的开始位置和长度
       int start = 0, minLen = INT_MAX;
       int left = 0, right = 0;
       
       unordered_map<char, int> window;
       unordered_map<char, int> needs;
       for (char c : t) needs[c]++;
       
       int match = 0;
       
       while (right < s.size()) {
           char c1 = s[right];
           if (needs.count(c1)) {
               window[c1]++;
               if (window[c1] == needs[c1]) 
                   match++;
           }
           right++;
           
           while (match == needs.size()) {
               if (right - left < minLen) {
                   // 更新最小子串的位置和长度
                   start = left;
                   minLen = right - left;
               }
               char c2 = s[left];
               if (needs.count(c2)) {
                   window[c2]--;
                   if (window[c2] < needs[c2])
                       match--;
               }
               left++;
           }
       }
       return minLen == INT_MAX ?
                   "" : s.substr(start, minLen);
   }

1. 找出字符串中 所有字母的异位词（字母相同但排序不同的字符串）

类比上一题，上题中只需要包含，这题是子串长度等于目标串长度。

   vector<int> findAnagrams(string s, string t) {
       // 用数组记录答案
       vector<int> res;
       int left = 0, right = 0;
       unordered_map<char, int> needs;
       unordered_map<char, int> window;
       for (char c : t) needs[c]++;
       int match = 0;
       
       while (right < s.size()) {
           char c1 = s[right];
           if (needs.count(c1)) {
               window[c1]++;
               if (window[c1] == needs[c1])
                   match++;
           }
           right++;
   
           while (match == needs.size()) {
               // 如果 window 的大小合适
               // 就把起始索引 left 加入结果
               if (right - left == t.size()) {
                   res.push_back(left);
               }
               char c2 = s[left];
               if (needs.count(c2)) {
                   window[c2]--;
                   if (window[c2] < needs[c2])
                       match--;
               }
               left++;
           }
       }
       return res;
   }

1. 无重复字符的最长字串

给定一个字符，找出不含重复字符的最长子串。

思路：先 向右移动right，若出现重复子串，向右移动left.

   int lengthOfLongestSubstring(string s) {
       int left = 0, right = 0;
       unordered_map<char, int> window;
       int res = 0; // 记录最长长度
   
       while (right < s.size()) {
           char c1 = s[right];
           window[c1]++;
           right++;
           // 如果 window 中出现重复字符
           // 开始移动 left 缩小窗口
           while (window[c1] > 1) {
               char c2 = s[left];
               window[c2]--;
               left++;
           }
           res = max(res, right - left);
       }
       return res;
   }

总结出的一般思想：

int left = 0, right = 0;

while (right < s.size()) {
    window.add(s[right]);
    right++;
    
    while (valid) {
        window.remove(s[left]);
        left++;
    }
}