【算法】滑动窗口思想解决数组OJ题目
基本思路
滑动窗口在很多地方都有实际使用,比如TCP的发送缓冲区就使用了这个思想来维护。
对于数组相关的算法OJ题来说,滑动窗口思路主要是基于双指针来实现的,一个作为窗口的左边界,一个作为窗口的右边界,并根据题目的条件来移动左右边界。
题目1-209-长度最小的子数组
第一题是leetcode的209,209. 长度最小的子数组 - 力扣(LeetCode),这也是滑动窗口的一个基础且经典的题目。
题干
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续
子数组 [numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回 0 。
1 | 示例 1: |
进阶:如果你已经实现 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都最多只能走一次,会漏掉这种情况。
代码
对于这类问题,可以用打印下标的方式进行调试。最终测试的时候记得把打印注释掉,因为它们很耗时,可能会导致你的答案超时。
1 | class Solution { |
说明一下,leetcode/牛客网上的代码击败人数是没有参考意义的,这个时间和你的网络状况也有关系。我的题解博客中贴出代码通过截图,是想告诉未来的读者,这个代码在我测试的时候是通过的,以免未来leetcode测试用例变化无法通过时产生误解。
好不容易搜到一个题解,结果它贴了无法通过的代码,谁看了不气?🤣
题目2-904-水果成篮
题干
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i]
是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
- 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
- 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。
给你一个整数数组 fruits ,返回你可以收集的水果的 最大 数目。
1 | 示例 1: |
思路
刚开始我都没有读懂这个题目,注意,输入参数中的数组并非每棵树上有几个种类的水果,而是每棵树上的水果是第几类。比如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。
1 | class Solution { |
题目3-76-最小覆盖子串
题干
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 ""
。
注意:
- 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
- 如果 s 中存在这样的子串,我们保证它是唯一的答案。
1 | 示例 1: |
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内没有符合条件的子串,此时返回空字符串。
代码
1 | class Solution { |
题目4-3-无重复字符的最长子串
题干
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
1 | 示例 1: |
提示:
1 | 0 <= s.length <= 5 * 104 |
思路
同样是用滑动窗口,还需要用一个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
(这个长度肯定小于已有的最大子串长度,所以无需更新最大子串长度);
- 因为sets中存在这个字符,所以right之前肯定还有一个
- right继续加加,重复上述步骤。
这里我还想到了可以用map代替set,这样就能直接找到上一个s[right]
字符的位置,不需要用left++遍历找。但仔细想了想,这个思路是错误的,因为每一次left++还需要将当前从滑动窗口中移除的数自set中删除,如果用map直接跳到上一个left的地方,最终还是需要遍历来删除left原始值和新值之间的数,并不能提高效率。
代码
1 | class Solution { |
The end
滑动窗口方法同时也是双指针法的一个运用,这三道题目都囊括了这个方法,平时记得加以复习。