滑动窗口方法解决子数组类问题

0 更新记录

2024-09-22: 初始版本

总结几道LeetCode上的使用滑动窗口方法解决的子串或者子数组类型的问题。

滑动窗口方法是一种模拟方法，思路是比较清晰的，使用左右指针（索引）维护一个窗口，在满足条件时收缩区间。具体实现上区间可以使用左闭右闭，也可以使用左闭右开等其他形式，我习惯使用左闭右闭的区间，所以下面的题目的代码实现都使用左闭右闭区间。

滑动窗口的过程可以概括为：

右指针不断向右扩展，窗口区间向右增大
左指针视情况收缩，一般是窗口内元素满足题目条件时收缩
左指针收缩至不满足上一步的条件
收缩过程中，或者收缩后，需要更新结果，结果可能是最大、最小元素个数（窗口区间长度），也可能是窗口内元素

比较困难的地方往往在于判断窗口内元素是否满足了左指针收缩的条件，这个条件决定了左指针什么时候收缩，什么时候停止收缩。

最后一步更新结果时，一般来说如果需要计算最小的窗口，则在收缩过程中更新；如果是计算最大的窗口，则在收缩结束后更新。

主要区别在于，左指针收缩时的窗口范围是否可能是一个结果。这样说可能不容易理解，在对比以下题目的解题思路中对结果更新时机的选择后，也会得到这个规律。209.长度最小的子数组和76.最小覆盖子串都是得到最小窗口；而3.无重复字符的最长子串和904.水果成篮是得到最大窗口。

下面的题目是按照思路由简单到复杂的顺序排列的，题解中的一些细节内容前面写过的后面题解可能就不会再重复提到。所以不建议直接看后面某道题的题解。

另外，题解中的代码几乎没经过精简，目的是尽可能的简化思路而不是压缩代码，比如取左指针指向的值并收缩左指针的代码x = nums[left++]，一般都会拆成{x = nums[left]; left++;}。

1 题目列表

LeetCode题目链接	本文小节链接
209.长度最小的子数组	209.长度最小的子数组
3.无重复字符的最长子串	3.无重复字符的最长子串
904.水果成篮	904.水果成篮
76.最小覆盖子串	76.最小覆盖子串
567.字符串的排列	567.字符串的排列

2 题解

209.长度最小的子数组

思路

本题是找满足条件的子数组问题，可以应用滑动窗口方法，窗口内的数组就是子数组。并且本题的条件给出的比较直白，需要维护的窗口所满足的条件就是数字总和大于等于target。

实现细节

按照前面总结的滑动窗口的基本步骤来看代码，[left, right]闭区间维护了一个子数组（窗口），sum记录了区间内元素的和，要求的结果是最小的子数组的长度result，求最小值，所以将其初始化为一个不可能取到的最大值，便于在程序中使用min更新。

从题目的数据范围来看，sum可能会超出int类型的最大值$2 ^ {31} - 1 = 2147483647$，但实测使用int可以通过。

使用for来拓展右侧区间，一般情况下的滑动窗口，右指针的向右拓展是不受条件限制的。右指针右移的结果就是加到区间里一个数sum += nums[right]，然后就需要检查窗口内元素是否满足题目条件。本题的条件就是窗口区间内的和是否大于等于target，停止收缩的条件是左侧扔掉某个值后，区间和小于target。

满足条件时应当收缩左侧区间，并且收缩区间可能不是向右移动一位就完成的，考虑右侧加入了一个很大的值，左侧可能需要扔掉好几个值才能停止收缩，所以收缩的过程应当使用while循环收缩。

收缩区间的操作包括：

更新区间最小长度result
在区间和中减去左侧即将扔掉的值
左指针右移

本题的result记录的是满足条件时的区间长度，所以应当在收缩中不断更新，收缩结束后的区间长度已经不满足区间和大于等于target这个条件。

最后返回时还需要注意是否会出现result从来没被更新的情况，类似样例3，输入数组所有值相加小于target。

代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;
        int sum = 0;
        int result = nums.size() + 1;
        for(int right = 0; right < nums.size(); right++) {
            sum += nums[right];
            while(sum >= target) {
                result = min(result, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        if(result != nums.size() + 1)
            return result;
        else
            return 0;
    }
};

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

思路

这是一个子串问题，也可以使用滑动窗口来解决。与上题不同的是，本题需要维护窗口内元素不重复。也就是说，本题左指针开始收缩的条件是窗口内的元素出现了重复，即右侧加入的新元素原本就在窗口中。左指针收缩的停止条件是，从左侧删除了与右侧刚加进来元素相同的那个元素。

实现细节

结合代码看一下实现的细节。需要记录窗口中都有哪些元素，哈希表是合适的数据结构，由于只需要记录元素的有无，这里使用集合unordered_set<char> window。右指针向右拓展是不需要条件的，直接使用for进行拓展。

左指针开始收缩的条件是右侧加入的字符ch在窗口中，即window.count(ch) != 0，收缩过程中不断从左侧删除字符，直到字符ch不在窗口中。

收缩过程中需要完成：

将左指针指向的字符从集合中移除
左指针向右收缩

还需要注意result的更新时机，这个题满足子串中无重复字符的条件是在收缩完成后才成立的，所以要在收缩结束后记录区间长度，并更新可能的最大长度result。和上一题的区别就在于，应当在区间收缩过程中满足结果条件，还是在区间收缩结束后满足结果条件。

最后一点就是在收缩结束后，将右侧刚加入的字符加入到集合里，这一步容易遗漏。那为什么不在刚开始就加入呢，如果右指针刚一拓展就加进来，window.count(ch) != 0这个条件就会一直成立，导致集合元素被删空。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        // 记录窗口内存在的字符
        unordered_set<char> window;
        int result = 0;
        int left = 0;
        for(int right = 0; right < n; right++) {
            char ch = s[right];
            // 新字符已在窗口中，收缩左侧区间，直到把新字符移除
            while(window.count(ch) != 0) {
                window.erase(s[left]);
                left++;
            }
            result = max(result, right - left + 1);
            window.insert(ch);
        }
        return result;
    }
};

904.水果成篮

思路

本题是一道LeetCode难度级别为中等的题目，但是结合了LeetCode机翻中文的混乱的题目描述，可以当成一道困难题了。

先整理一下题意：

共有2个篮子，同一个篮子中只能装同种类的水果，共有n = fruits.size()颗树，每棵树最多能摘一个水果，每棵树的水果类型记录在输入的fruits数组中，问最多能装多少水果。

对于这种问题，容易产生一个思路上的误区，就是当成一个取最优的问题去考虑使用动规等方法把问题复杂化。像最基本的在数组中找最大值一样，对数组进行遍历，最终得到的是曾经遍历过的最大值，而并不需要刚好计算出最大值。

对于这个题，思路就是用滑动窗口遍历所有的树，始终确保窗口中树的种类不超过两种，遍历过程中记录满足种类不超过两种时的窗口长度，遍历结束后也就得到了最大的窗口长度，也就是最多能获取多少水果。

对于任意一棵树，如果两个篮子中已经装了和他类型相同的水果，那就可以摘一个水果。如果没有装过这个种类，那就把已有的最先装的那一类全部丢掉，装新的这一类。

实现细节

根据思路中的分析，使用一个哈希表来存储窗口中的水果的种类和个数unordered_map<int, int> window，key表示水果种类，其value表示这种水果有几个。

右指针使用for向右移动，每次加入一棵新树，并将新树的水果种类加入哈希表，并将水果个数自增一次。

左指针收缩的条件是，当窗口内的水果种类超过两种，左指针就要开始收缩，直到种类数不超过两种时停止。

收缩过程需要完成：

将左指针指向的水果的个数减一，左指针右移表示会扔掉左指针指向的那棵树的水果。
如果这个种类的水果数已经为0，说明这个种类已经被移除，在哈希表中删除这个键。
右移一次左指针。

最后结果result的更新时机和3.无重复字符的最长子串是类似的，左指针移动结束后才满足记录结果的条件，即满足窗口内水果种类不超过两种，所以应当在while循环结束之后更新result。

代码

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        unordered_map<int, int> window;
        int left = 0;
        int result = -1;
        for (int right = 0; right < n; right++) {
            window[fruits[right]]++;
            while (window.size() > 2) {
                int key = fruits[left];
                window[key]--;
                if (window[key] == 0) {
                    window.erase(key);
                }
                left++;
            }
            result = max(result, right - left + 1);
        }
        return result;
    }
};

小优化

这个题目需要存储窗口内的水果种类，上面方法中用到了哈希表，不过由于种类只有两个，只有在新种类加入，旧的种类尚未删除时才可能会出现三个种类，用哈希表似乎有些浪费。可以使用两个变量type_a, type_b来记录窗口中的两个种类。

右指针扩展时，判断新加入的水果是否是第三个种类：if (fruits[right] != type_a && fruits[right] != type_b)。

上述判断成立则说明fruits[right]是一个新的种类，而fruits[right-1]一定是不同于fruits[right]的种类。更新窗口内的种类为type_a = fruits[right - 1]，type_b = fruits[right]。此时窗口内的种类实际上有三种，应当保留的是新加进来的type_a，和前面一个种类type_b，更前面的种类应当被删去，删除这个种类就是右移左指针收缩左区间的任务。

之前方法中，通过不断检查哈希表中的键个数来判断是否应该停止左侧收缩，但这个方法中，我们只记录了两个种类。所有应当在窗口中遍历删除所有种类不是type_a和type_b的水果。删除的方法是从right-1开始向左找第一个左侧不是type_a的树，这个位置就应当是左指针的新位置。

为什么从右往左找左指针的新位置？

考虑这样的例子fruits = [1, 2, 1, 2, 3, 4]:

为什么从右往左找左指针的新位置

左指针指向1（index=0），当right指向3（index=4）时，type_b更新为3，type_a更新为2，需要删除所有种类1，即index=[0, 1, 2]三个元素都要删除，左指针应当更新到2（index=3）的位置。

如果直接将左指针从左到右遍历，遇到2（index=1）时便会停止，不能到达正确的位置，所有要从right-1（index=3）开始，向左找第一个左边元素不是type_a的位置，即index=3。

优化后的代码

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        int left = 0;
        int type_a = fruits[0];
        int type_b = fruits[0];
        int result = -1;
        for (int right = 0; right < n; right++) {
            if (fruits[right] != type_a && fruits[right] != type_b) {
                type_a = fruits[right - 1];
                type_b = fruits[right];
                left = right - 1;
                while (left >= 1 && fruits[left - 1] == type_a)
                    left--;
            }
            result = max(result, right - left + 1);
        }
        return result;
    }
};

76.最小覆盖子串

思路

子串问题，考虑使用滑动窗口。关键问题是确定什么时候收缩左指针，收缩至什么时候停止。

对于这个题目，当右指针扩展到窗口中字符包含了子串t中所有的字符，并且对于t中的重复字符，窗口中对应字符个数也要大于等于t中的个数时，可以开始收缩左侧区间。一直收缩到不满足这个“包含”关系为止。

实现细节

结合代码说明一些细节。“包含”关系的判断是本题的核心，判断一个元素在不在集合中，使用哈希表。这里使用一个哈希表unordered_map<char, int> need记录目标子串t中需要的字符及需要的个数，使用另一个哈希表unordered_map<char, int> window记录窗口中包含的字符及个数。

“包含”关系可以转化为：need中的每个键都在window中，并且对应的值都满足window[key] >= need[key]。

窗口右指针向右拓展，每次将右侧加入的字符加入到window哈希表中，加入后应当对是否满足“包含”关系进行判断，也就是说要判断是否要收缩左指针。这时发现按照刚才的思路，判断包含关系要遍历need哈希表，右指针每次移动，都需要做一次这样的判断，这个判断“包含”的功能可以用一个单独的函数实现。

在移动右指针遍历s字符串时，不在子串t中的字符是没有任何作用的，将其放入window表中也没有什么作用。下面程序在取到右指针指向的字符后，首先就对其是不是子串中的字符进行判断，如果不是，直接跳过这个字符if(need.count(ch) == 0) continue;。

在收缩左指针时也做了同样的处理，遇到不关心的字符之间跳过。这种提前返回、跳过的策略有时能一定程度简化后序程序的判断逻辑。

这里可以略做优化，使用一个变量need_n来记录子串需要几个字符，或者解释为，子串中还有几个字符没有满足“包含”关系，初始化为子串中不同字符的长度，也就是子串构成的need哈希表的键个数。

对于一个右侧加入的字符ch，加入window表后，当window[ch] == need[ch]时，表示这个字符满足了“包含”关系，即ch在window中，并且数量恰好相等。此时将need_n自减一次，子串中不满足“包含”关系的字符减少一个。

这里需要说明，为什么不能使用window[ch] >= need[ch]?

如图例所示，如果使用>=，当右指针遇到已经加入到window的字符时，会因为>的成立而导致need_n意外的减少，会使左指针在不该收缩的时候收缩，出现错误。

为什么从右往左找左指针的新位置

只有在恰好满足window[ch] == need[ch]条件那一次需要减少need_n。

使用上述方法，当need_n == 0时表示窗口中的字符串已经“覆盖”了子串，此时可以开始收缩左侧区间。

收缩左指针需要做的事情：

检查左指针指向的字符ch，如果不在need中，左指针右移后直接跳过这个字符，进行下一个字符的判断。
字符ch在window中的数量自减。
如果ch在window中的数量比need数量小，自增need_n为1，含义是子串中有1个字符ch不满足“包含”关系。

最后关于结果的更新时机，本题和209.长度最小的子数组情况相似，收缩过程中是满足题目的“覆盖”条件的，所以记录结果的两个变量min_len和min_left的更新放在收缩左指针的while循环内部，这两个变量分别记录主串s中能覆盖子串的最短的子串长度和其起始位置。

同样可能会存在从来没有收缩过左指针的情况，例如样例3：s = “a”, t = “aa”，也就从来没有更新过变量min_len和min_left，此时要对这两个变量是否被更新过进行检查后再输出最终结果。

代码

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size();
        // 需要的字符及其个数
        unordered_map<char, int> need;
        // 窗口内有的字符及个数
        unordered_map<char, int> window;
        for(char c : t) {
            need[c]++;
        }
        // 总共缺少的字符数
        int need_n = need.size();
        // 记录结果，最短子串的起始位置和长度
        int min_len = n + 1;
        int min_left = 0;
        // 双指针维护滑动窗口
        int left = 0;
        for(int right = 0; right < n; right++) {
            char ch = s[right];
            if(need.count(ch) == 0) continue;
            window[ch]++;
            // 现有的满足需要的，将总缺少的字符数减一
            if(window[ch] == need[ch]) {
                need_n--;
            }
            // 没有缺少的字符数，即满足条件，左侧向右收缩
            while(need_n == 0) {
                // 更新最小长度
                if(min_len > right - left + 1) {
                    min_left = left;
                    min_len = right - left + 1;
                }
                // 检查左侧扔掉的字符
                ch = s[left];
                left++;
                if(need.count(ch) == 0) continue;
                window[ch]--;
                // 收缩后不够了
                if(window[ch] < need[ch]) {
                    need_n++;
                }
            }
        }
        if(min_len == n + 1)
            return "";
        else
            return s.substr(min_left, min_len);
    }
};

优化：少用一个哈希表

TBD

567.字符串的排列

思路

本题和上一题76.最小覆盖子串思路非常相近，都是主串“覆盖”子串类型的问题，本题只需要判断能否覆盖，不需要记录最小满足要求的子串，所以在遍历时，如果遇到满足条件可以直接返回。

实现细节

几乎完全复制了上一题的代码，只是在上一题更新最小长度位置修改为判断当前窗口长度是否为子串s1长度，如果是则说明此时满足了：

主串中的窗口[left, right]中的每一个字符都在子串之中，并且对应字符的个数也相同
主串窗口与子串等长

这就说明在主串中找到了子串的排列。

代码

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s2.size();
        // 需要的字符及其个数
        unordered_map<char, int> need;
        // 窗口内有的字符及个数
        unordered_map<char, int> window;
        for(char c : s1) {
            need[c]++;
        }
        // 总共缺少的字符数
        int need_n = need.size();
        // 双指针维护滑动窗口
        int left = 0;
        for(int right = 0; right < n; right++) {
            char ch = s2[right];
            if(need.count(ch) == 0) continue;
            window[ch]++;
            // 现有的满足需要的，将总缺少的字符数减一
            if(window[ch] == need[ch]) {
                need_n--;
            }
            // 没有缺少的字符数，即满足条件，左侧向右收缩
            while(need_n == 0) {
                // 没有缺少的字符数，直接返回
                if(right - left + 1 == s1.size()) {
                    return true;
                }
                // 检查左侧扔掉的字符
                ch = s2[left];
                left++;
                if(need.count(ch) == 0) continue;
                window[ch]--;
                // 收缩后不够了
                if(window[ch] < need[ch]) {
                    need_n++;
                }
            }
        }
        return false;
    }
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。