引言

滑动窗口实际上也属于双指针的技巧范畴，利用两个指针圈定了一个范围。思想简单，但是细节满满，比如什么时候需要扩大窗口（right++），什么时候需要缩小窗口（left++），什么时候更新数据。主要就是这几点，把这几点弄清楚了，那么滑动窗口的问题也就解决了。

适合解决的问题

滑动窗口适合于解决连续的子数组，子串等问题，并不适合于解决非连续性的问题。

基本的框架

int left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;

    // 更新窗口数据
    
    // 是否满足窗口缩小条件，满足的话，缩小窗口，并更新窗口数据
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }

    // 更新最终的结果数据
}

无重复字符的最长子串

这是leetcode的一道题目。我们下面分析下

首先我们需要一个hash表来存放窗口中的数据，因为是无重复子串，所以每个字符出现一次，可以用unordered_map
当right向右滑动扩大窗口时，给窗口的unordered_map增加数据
然后判断窗口是否应该收缩了，如果是，则将left向滑动，然后更新unordered_map减少数据，
最后更新结果数据

具体的代码逻辑如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0;
        int right = 0;

        int ret = 0;
        unordered_map<char, int> windows;
        while (right < s.length()) {
            // 扩大窗口
            char c = s[right];
            windows[c]++;
            right++;

            // 检查是否满足收缩条件，然后开始收缩
            while (windows[c] > 1) {
                char d = s[left];
                windows[d]--;
                left++;
            }

            // 收缩完毕后，开始更新数据
            ret = max(ret, right - left);
        }
        return ret;
    }
};

我们来看细节，扩大窗口的时候，直接将c更新到窗口中，然后直接判断是否需要收缩，而收缩也是直接对c进行while循环，如果条件成立，那就是因为新增加了c导致窗口需要收缩（否则在之前添加元素的时候就收缩了），所以才会是while (windows[c] > 1)，在循环内部不停的收缩窗口，知道满足条件。这是说明窗口是满足条件的，需要计算ret的最大值。

最小覆盖子串

对于这个题目，处理的是连续的子串，因此用滑动窗口是非常合适的。那么自然的按照滑动窗口的套路：

right不停的向右扩张，直到窗口的子串符合条件，right停止扩张
然后left向右扩张，直到窗口中的子串不再符合条件，left停止扩张
然后重复上面的过程，直到right到达终点

有两个需要注意的点

怎样判定窗口中的子串复合条件，我们可以用一个unordered_map存放窗口中的数据，每次为窗口新增数据时，判断是否满足right停止扩张条件
需要新增一个标志valid来决定right和left的扩张与停止

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> needs;
        for (auto item : t) {
            needs[item]++;
        }

        int minLen = INT_MAX;
        int startPos = 0;

        int left = 0;
        int right = 0;
        int valid = 0;
        unordered_map<char, int> windows;  // 用来存放满足needs条件的char
        while (right < s.length()){
            char c = s[right++];
            if (needs.count(c)) { // 当字符属于needs的情况下，才会将其放入windows，这种字符满足数目要求时，才会valid++
                windows[c]++;
                if (windows[c] == needs[c]) {
                    valid++;
                }
            }

            while(valid == needs.size()) {  // 所有的字符数目都满足时，才能进行left缩放
                if (right - left < minLen) {
                    minLen = right - left;
                    startPos = left;
                }
                char d = s[left++];
                if (needs.count(d)) { // 字符满足needs要求时，才能更新windows数据，否则只需要left++即可，窗口可以尽情向右滑动
                    if (windows[d] == needs[d]) {
                        valid--;
                    }
                    windows[d]--;
                }
            }
        }
        return minLen == INT_MAX ? "" : s.substr(startPos, minLen);
    }
};

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

这个题目用上面的思路也是可以解决的，主要有一点需要注意

这个题目是一个固定大小的窗口，这会相对简单一些

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;

        unordered_map<char, int> needs;
        for (auto item : p) {
            needs[item]++;
        }

        int left = 0;
        int right = 0;
        int valid = 0;
        unordered_map<char, int> windows;
        while (right < s.length()) {
            char c = s[right++];
            if (needs.count(c)) {
                windows[c]++;
                if (windows[c] == needs[c]) {
                    valid++;
                }
            }

            while (right - left == p.length()) { // 固定大小窗口
                if (valid == needs.size()) {
                    ret.push_back(left);
                }
                char d = s[left++];
                if (needs.count(d)) {
                    if (windows[d] == needs[d]) {
                        valid--;
                    }
                    windows[d]--;
                }
            }
        }
        return ret;
    }
};

字符串的排列

这道题目跟上面的找到字符串中所有字母异位词基本是一个意思，实际上这还是一个弱化版本的。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char, int> needs;
        for (auto item : s1) {
            needs[item]++;
        }

        int left = 0;
        int right = 0;
        int valid = 0;
        unordered_map<char,int> windows;
        while (right < s2.length()) {
            char c = s2[right++];
            if (needs.count(c)) {
                windows[c]++;
                if (windows[c] == needs[c]) {
                    valid++;
                }
            }

            if (right - left == s1.length()) {
                if (valid == needs.size()) {
                    return true;
                }
                char d = s2[left++];
                if (needs.count(d)) {
                    if (needs[d] == windows[d]) {
                        valid--;
                    }
                    windows[d]--;
                }
            }
        }
        return false;
    }
};

长度最小的子数组

前面的例题主要是字符串的内容，下面我们看一个数组的问题。这个题目还是比较简单的。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int minLen = INT_MAX;

        int left = 0;
        int right = 0;
        int sum = 0;
        while (right < nums.size()) {
            sum += nums[right++];
            while (sum >= target) {
                if (minLen > right - left) {
                    minLen = right - left;
                }
                sum -= nums[left++];
            }
        }
        return minLen == INT_MAX ? 0 : minLen;

    }
};