滑动窗口大致逻辑：

int left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

滑动窗口算法框架：

void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (const char &c : t) need[c]++;
 
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
 
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

套模板时考虑以下四个问题：

• 当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
• 什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
• 当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
• 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

---

3. 无重复字符的最长子串✅

暴力：用map维护窗口内的字符不重复，每次重新计数只让左边界+1

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(!s.size()) return 0;

        unordered_map<char, int> mp;
        int left = 0, right = 1;
        int res = 1;

        mp[s[0]] = 1;
        while(left < right && right < s.size()) {
            if(mp[s[right]] != 1) {
                mp[s[right]] = 1;
                res = max(res, right - left + 1);
                right++; 
                // printf("res = %d right = %d left = %d\n", res, right, left);
            } else {
                left++;
                mp.clear();
                mp[s[left]] = 1;
                right = left + 1;
            }
            
        }

        return res; 
    }
};

---

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

用substr逐步构造子串与p比较，超时

滑动窗口

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        unordered_map<char, int> need, window;
        for(const auto &c : p) {
            need[c]++;
        }
        
        int left = 0, right = 0;
        int vaild = 0;
        while(right < s.size()) {
            //右窗口更新
            char rc = s[right++];
            if(need.count(rc)) {
                window[rc]++;
                if(need[rc] == window[rc]) vaild++;
            }
       
            //判断左窗口更新
            while(right - left >= p.size()) {
                if(vaild == need.size()) { //注意是need的长度而不是p
                    res.push_back(left);
                }
                char lc = s[left++];
                if(need.count(lc)) {
                    if(need[lc] == window[lc]) vaild--;
                    window[lc]--;
                }
            }
        }

        return res; 
    }
};

---

560. 和为 K 的子数组❌

*以为是滑动窗口（因为有负数不好处理），实则是前缀和*

*+哈希（相当于1. 两数之和）*

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int res = 0;
        unordered_map<int, int> mp;
        vector<int> preSum;
        preSum.resize(nums.size() + 1);

        preSum[0] = 0; //注意要空一个0，否则会漏掉示例1的第一个子数组或者自身一个数就满足的情况
        for(int i = 0; i < nums.size(); i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        for(int i = 0; i < preSum.size(); i++) {
            cout << preSum[i] << " ";
            int cnt = mp[preSum[i] - k];
            if(cnt) {
                res += cnt;
                // cout << "->yes ";
            }
            mp[preSum[i]]++;  
        }
         
        return res;
    }
};

---

239. 滑动窗口最大值❌

自定义单调队列

class Solution {
private:
    class MyQueue {
    public:
        deque<int> dq;
        void pop(int x) {
            if(!dq.empty() && dq.front() == x) dq.pop_front();
        }
        void push(int x) {
            while(!dq.empty() && x > dq.back()) dq.pop_back();     
            dq.push_back(x);
        }
        int front() {
            return dq.front();
        }
    };
public:   
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        MyQueue que;
        for(int i = 0; i < k; i++) que.push(nums[i]);
        res.push_back(que.front());
        for(int i = k; i < nums.size(); i++) {
            que.pop(nums[i-k]);
            que.push(nums[i]);
            res.push_back(que.front());
        }
        
        return res;
    }
};

---

76. 最小覆盖子串❌

滑动窗口经典题

class Solution {
public:
    string minWindow(string s, string t) {
        // key是字符，value是个数；need是t的字符，window是当前窗口的字符
        unordered_map<char, int> need, window;
        for(auto &c : t) need[c]++;

        int left = 0;
        int valid = 0;
        string res;
        // 最好不要用while循环，因为right是在每次循环最后，即统计完之后才++
        for(int right = 0; right < s.size(); right++) {
            // 更新右边界
            char ch = s[right];
            window[ch]++;
            // window[ch]至少为1，如果window[ch] <= need[ch]，说明ch是需要的字符(属于t)
            if(window[ch] <= need[ch]) { 
                valid++;
            }
            // 更新左边界
            while(window[s[left]] > need[s[left]]) { // 如果左边界字符多余了
                window[s[left]]--;
                left++;
            }
            // 已经覆盖
            if(valid == t.size()) {
                if(res.size() == 0 || right - left + 1 < res.size()) {
                    res = s.substr(left, right - left + 1);
                }
            }
            // 不用把valid重置为0，只需等右边界找到替代品，左边界自然会缩，res就会更新
        }
        return res;
    }
};