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

基本思路

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

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

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

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

题干

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

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

示例 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)。

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

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

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

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

代码

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

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 棵树上的水果 种类 。

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

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

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

示例 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来保存最长的数字个数，作为题目返回值。

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

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

代码

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

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 中存在这样的子串，我们保证它是唯一的答案。

示例 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字符串内字符的个数。

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

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

代码

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 ，请你找出其中不含有重复字符的 最长子串 的长度。

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

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

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

提示：

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原始值和新值之间的数，并不能提高效率。

代码

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

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