【算法】滑动窗口思想解决数组 OJ 题目

距离上次更新本文已经过去了 369 天，文章部分内容可能已经过时，请注意甄别

基本思路

滑动窗口在很多地方都有实际使用，比如 TCP 的发送缓冲区就使用了这个思想来维护。

对于数组相关的算法 OJ 题来说，滑动窗口思路主要是基于双指针来实现的，一个作为窗口的左边界，一个作为窗口的右边界，并根据题目的条件来移动左右边界。

题目 1-209 - 长度最小的子数组

第一题是 leetcode 的 209，209. 长度最小的子数组 - 力扣（LeetCode），这也是滑动窗口的一个基础且经典的题目。

题干

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的连续
子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

plaintext

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

进阶：如果你已经实现 O(n) 时间复杂度的解法，请尝试设计一个 O(n * log(n)) 时间复杂度的解法。

思路

这道题要求的是数组中加起来大于等于 target 的最小连续子数组。最简单的办法是暴力两次遍历来计算每一个子数组组合的和，再与目标 target 对比，但这样的时间复杂度是 O(N^2)。

使用滑动窗口来解决这道题才是对的，思路如下。

left 和 right 作为滑动窗口的左右边界，以 right 作为 for 循环的自增；
right++ 遍历一个数（滑动窗口扩张），加入到 sum 中；
如果 sum 大于等于 target，记录 right-left+1 为当前子数组长度，开始操作 left；
left++ 遍历一个数（滑动窗口缩限），将其从 sum 中删除；
再次判断 sum 是否大于等于 target，如果大于，继续执行第三部和第四步；
sum 不大于 target 了，停止操作 left，继续 for 循环操作 right，移动右边边界；
right 大于等于下标，循环结束。

最终得到的 len 就是最短的子数组。

注意，操作 left 的时候要用 while 循环，而不是用 if 来操作，因为最终可能会遇到，right 固定在数组的最后一位，但 left 还能继续往前走的情况。如果使用 if，那么每个循环中 left 都最多只能走一次，会漏掉这种情况。

代码

对于这类问题，可以用打印下标的方式进行调试。最终测试的时候记得把打印注释掉，因为它们很耗时，可能会导致你的答案超时。

cpp

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0,right=0; // 滑动窗口
        int minRange = INT32_MAX; // 因为需要获取最小值，所以要用一个最大值来比较
        int sum = 0;
        for(right =0;right<nums.size();right++)
        {
            sum += nums[right];
            while(sum >= target) // 这里必须要用while，需要考虑right是最后一个但left还可以继续走的情况
            {
                //cout << "fix: " << left << " - " << right << " sum:" << sum << "\n";
                int curDiff = right - left + 1; // 当前长度
                minRange = min(minRange,curDiff);
                sum -= nums[left];
                left ++;// 左侧缩限
            }
            //cout << "all: " << left << " - " << right << " sum:" << sum << "\n";
        }
        // 如果还是最大值，则返回0
        return minRange == INT32_MAX ? 0 : minRange;
    }
};

说明一下，leetcode / 牛客网上的代码击败人数是没有参考意义的，这个时间和你的网络状况也有关系。我的题解博客中贴出代码通过截图，是想告诉未来的读者，这个代码在我测试的时候是通过的，以免未来 leetcode 测试用例变化无法通过时产生误解。

好不容易搜到一个题解，结果它贴了无法通过的代码，谁看了不气？🤣

题目 2-904 - 水果成篮

904. 水果成篮 - 力扣（LeetCode）

题干

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

plaintext

示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

思路

刚开始我都没有读懂这个题目，注意，输入参数中的数组并非每棵树上有几个种类的水果，而是每棵树上的水果是第几类。比如 fruits[0] = 1 代表第 0 棵树上的水果是种类 1，fruits[1] = 2 代表第 1 棵树上的水果是种类 2。

我刚开始错误的理解为元素 2 代表这棵树上有两种不同的水果，如果这样理解这道题就没法写了……

你的篮子里面一次只能装两个种类的水果，这样这道题就转变成了，给出的数组中只包含两个相同数字的最长子数组。

比如数组 [3,3,3,1,2,1,1,2,3,3,4]，最长只包含两个数字的子数组是 [1,2,1,1,2]；数组 [1,2,3,2,2] 最长只包含两个数字的子数组是 [3,2,2]；

同样是用滑动窗口来解题，使用 left/right 左右边界，right 作为 while 循环条件，并设置一个数字种类计数器 fruitsCount、数字个数计数器 sizeCount 和一个 set 来保存当前的两个数字。另外还需要一个 maxSizeCount 来保存最长的数字个数，作为题目返回值。

right 遍历，当当前数字不存在 set 中，且 count 小于 2 时，将其加入到 set 中，并将 fruitsCount++，长度 sizeCount++，使用 sizeCount 对比更新 maxSizeCount；
当当前数字存在于 set 中，长度 sizeCount++，使用 sizeCount 对比更新 maxSizeCount；
当当前数字不存在于 set 中，且 fruitsCount 已经为 2，说明当前走到了第三个数字的位置，重置 set 和 fruitsCount，使用 sizeCount 对比更新 maxSizeCount 后，将 sizeCount 重置为 0；
left++（滑动窗口左侧缩限），一直加加到和当前数字不同的位置（比如 left 当前处于 3,3,3,1,2 的 3 的位置，那么就需要移动到 1 的位置，过滤重复数据）；
right 重置到 left 的位置，继续执行上述步骤，直到 right 走完数组。

注意，每次 sizeCount++ 之后，都需要和 maxSizeCount 对比并更新。否则如果给出的数组本来就只有两种数字（比如 [1,2,1] 这整个数组本身就是答案）的情况，maxSizeCount 会没有正常更新。

代码

因为本题目的 set 并不需要排序，所以使用哈希 set 会优于红黑树的 set。

cpp

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_set<int> fruitsSet;
        int fruitsCount = 0; // 种类数量
        int curCount = 0; // 当前水果计数
        int retCount = -1;

        int left = 0,right = 0;
        while(right < fruits.size())
        {
            // 水果不在里面，且还没有2个
            if(fruitsCount < 2 && fruitsSet.count(fruits[right]) == 0){
                fruitsCount++; // 种类数量加一
                fruitsSet.insert(fruits[right]);
                curCount++; // 水果个数加一
                right++;
                retCount = max(curCount,retCount);
                // cout << right << " - " << fruits[right] << "\n";
            }
            // 水果在里面
            else if(fruitsCount <= 2 && fruitsSet.count(fruits[right]) != 0)
            {
                right++;
                curCount++;
                retCount = max(curCount,retCount);
            }
            // 水果不在里面，且已经有两个了
            else if(fruitsCount >= 2 && fruitsSet.count(fruits[right]) == 0)
            {
                retCount = max(curCount,retCount);
                fruitsSet.clear(); // 清空
                curCount = 0;
                fruitsCount = 0;
                // 找下一个和left当前不同的水果
                while(left < fruits.size() && fruits[left+1] == fruits[left]){
                    left++;
                }
                // 还需要再走一步，才是和刚刚不一样的水果
                left++;
                right = left; // 重新开始新一轮计数
            }
        }
        return retCount;
    }
};

题目 3-76 - 最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

题干

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

plaintext

示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

s 和 t 由英文字母组成，且可能会重复（未规定大小写）

思路

同样是使用滑动窗口，但这一次的缩限需要进行判断。

首先要明白题目给出的条件

当 t 字符串长度大于 s 字符串的时候，直接返回空，因为 s 的子串无法包含 t；
t 中的字母可能是大写也可能是小写，而且 t 中的某个字母可能会重复，所以需要一个 map 来保存 t 字符串的字符及其个数；
题目要求返回的是子串，所以需要记录子串在 s 内的起始下标及其长度（使用 substr 函数来处理）；

这里需要用到两个哈希 map，一个 tMaps 用于存放 t 字符串中的所有字符和个数，另外一个 curMaps 用来存放当前滑动窗口内包含的 t 字符串内字符的个数。

right++，当遇到 t 字符串内的字符，则将 curMaps 中对应字符数量加一；
检查 curMaps 中的字符个数是否都已经大于等于 tMaps 中的字符数量，且没有缺少字符；
如果符合条件，记录当前的 left（作为子串起始位置）和长度 len，随后 left++ 开始缩限，并将 curMaps 中对应字符减一，直到 curMaps 不符合条件为止；
right 继续加加，重复上述步骤，直到 right 越界。

注意，这里建议将用于更新的子串起始地址 begin 初始化为非法下标 -1，并在 return 的时候进行判断，这样能知道 s 字符串中是否存在符合条件的子串。如果 begin 在循环结束后还是 -1，则代表 s 内没有符合条件的子串，此时返回空字符串。

代码

cpp

class Solution {
public:
    // 判断当前map中是否已经包含目标map中需要的所有字符
    bool statusCheck(const unordered_map<char,int>& tMaps,unordered_map<char,int>& curMaps)
    {
        for(auto&e:tMaps){
            // 这里不能用不等于判断，因为curMaps中的计数器大于的时候也是符合条件的
            if(curMaps.count(e.first)!=0 && curMaps[e.first] < e.second){
                return false;
            }
            else if (curMaps.count(e.first)==0)
            {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        if(t.size() > s.size()){
            return "";
        }

        int left = 0,right = 0;
        int begin = -1, end = -1, len = INT32_MAX; // 最终用于返回结果的下标区间
        // 记录t中每个字符出现的次数
        unordered_map<char,int> tMaps;
        for(auto&e:t){
            tMaps[e]++;
        }
        // 当前出现的tmap中的字符的数量
        unordered_map<char,int> curMaps;
        while(right < s.size())
        {
            // 如果目标map里面有，则在当前map里面将数量加一
            if(tMaps.count(s[right]) !=0){
                curMaps[s[right]]++;
            }
            // 如果符合条件，则缩限到不能缩限为止
            while(statusCheck(tMaps,curMaps) && left <=right)
            {
                // 如果长度小于当前记录的长度，则更新
                if(right - left + 1 < len)
                {
                    len = right - left + 1;
                    begin = left;
                    end = right;
                }
                // 在目标map里面看是否有这个字符，有则在当前map中将数量减一
                if(tMaps.count(s[left]) !=0){
                    curMaps[s[left]]--;
                }
                left++;
            }
            right++;
        }
        // 如果begin没有被更新，则说明不存在
        return begin == -1 ? "" : s.substr(begin,len);
    }
};

题目 4-3 - 无重复字符的最长子串

题干

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

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

plaintext

示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

plaintext

1 2	0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成

思路

同样是用滑动窗口，还需要用一个 unordered_set 来记录某个字符是否已经存在于窗口内了。用 for 循环来扩张 right 右边界，left 左边界在情况不符合的时候再缩限：

sets 不存在 s[right] 字符，当前子串长度加一，并更新最大子串长度；
sets 存在 s[right] 字符，left 开始缩限：
- 因为 sets 中存在这个字符，所以 right 之前肯定还有一个 s[right] 字符；
- 将 s[left] 的元素从 sets 中移除，直到 left++ 走到上一个和 s[right] 相等的字符处；
- 循环终止时 left 走到上一个 s[right] 的位置，left 再加一走到下一位，更新当前子串长度为 right-left+1（这个长度肯定小于已有的最大子串长度，所以无需更新最大子串长度）;
right 继续加加，重复上述步骤。

这里我还想到了可以用 map 代替 set，这样就能直接找到上一个 s[right] 字符的位置，不需要用 left++ 遍历找。但仔细想了想，这个思路是错误的，因为每一次 left++ 还需要将当前从滑动窗口中移除的数自 set 中删除，如果用 map 直接跳到上一个 left 的地方，最终还是需要遍历来删除 left 原始值和新值之间的数，并不能提高效率。

代码

cpp

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0){
            return 0;
        }
        int maxLength = -1;
        int curLength = 0;
        int left = 0,right = 0;
        unordered_set<char> sets;
        for(right = 0;right<s.size();right++)
        {
            // 找不到插入
            if(sets.count(s[right]) == 0){
                sets.insert(s[right]);
                curLength++;
                maxLength = max(maxLength,curLength);
                continue;
            }
            // 找到了，左侧缩限到上一个s[right]的位置
            while(s[left] != s[right])
            {
                // 每一次缩限都需要把字符从set删除
                sets.erase(s[left]);
                left++;
            }
            // 走到了上一个s[right]，需要再走一次
            left++;
            curLength = right-left+1;
            // 这里不需要修改sets，把原有的s[right]当作新插入的
        }

        return maxLength;
    }
};

The end

滑动窗口方法同时也是双指针法的一个运用，这三道题目都囊括了这个方法，平时记得加以复习。

基本思路

题目 1-209 - 长度最小的子数组

题干

思路

代码

题目 2-904 - 水果成篮

题干

思路

代码

题目 3-76 - 最小覆盖子串

题干

思路

代码

题目 4-3 - 无重复字符的最长子串

题干

思路

代码

The end

微信扫一扫：分享