笔者最早接触滑动窗口是滑动窗口协议
,滑动窗口协议(Sliding Window Protocol),属于 TCP 协议的一种应用,用于网络数据传输时的流量控制,以避免拥塞的发生。发送方和接收方分别有一个窗口大小 w1 和 w2。窗口大小可能会根据网络流量的变化而有所不同,但是在更简单的实现中它们是固定的。窗口大小必须大于零才能进行任何操作。
我们算法中的滑动窗口也是类似,只不过包括的情况更加广泛。实际上上面的滑动窗口在某一个时刻就是固定窗口大小的滑动窗口,随着网络流量等因素改变窗口大小也会随着改变。接下来我们讲下算法中的滑动窗口。
滑动窗口是一种解决问题的思路和方法,通常用来解决一些连续问题。比如 LeetCode 的 209. 长度最小的子数组。更多滑动窗口题目见下方题目列表
。
滑动窗口主要用来处理连续问题。比如题目求解“连续子串 xxxx”,“连续子数组 xxxx”,就应该可以想到滑动窗口。能不能解决另说,但是这种敏感性还是要有的。
从类型上说主要有:
后面两种我们统称为可变窗口
。当然不管是哪种类型基本的思路都是一样的,不一样的仅仅是代码细节。
对于固定窗口,我们只需要固定初始化左右指针 l 和 r,分别表示的窗口的左右顶点,并且保证:
对于可变窗口,我们同样固定初始化左右指针 l 和 r,分别表示的窗口的左右顶点。后面有所不同,我们需要保证:
形象地来看的话,就是 r 指针不停向右移动,l 指针仅仅在窗口满足条件之后才会移动,起到窗口收缩的效果。
以下是 209 题目的代码,使用 Python 编写,大家意会即可。
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
l = total = 0
ans = len(nums) + 1
for r in range(len(nums)):
total += nums[r]
while total >= s:
ans = min(ans, r - l + 1)
total -= nums[l]
l += 1
return 0 if ans == len(nums) + 1 else ans
以下题目有的信息比较直接,有的题目信息比较隐蔽,需要自己发掘
[1]
【Python,JavaScript】滑动窗口(3. 无重复字符的最长子串): https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/pythonjavascript-hua-dong-chuang-kou-3-wu-zhong-fu/
[2]
76. 最小覆盖子串: https://leetcode-cn.com/problems/minimum-window-substring/solution/python-hua-dong-chuang-kou-76-zui-xiao-fu-gai-zi-c/
[3]
209. 长度最小的子数组: https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/209-chang-du-zui-xiao-de-zi-shu-zu-hua-dong-chua-2/
[4]
【Python】滑动窗口(438. 找到字符串中所有字母异位词): https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/python-hua-dong-chuang-kou-438-zhao-dao-zi-fu-chua/
[5]
【904. 水果成篮】(Python3): https://leetcode-cn.com/problems/fruit-into-baskets/solution/904-shui-guo-cheng-lan-python3-by-fe-lucifer/
[6]
【930. 和相同的二元子数组】(Java,Python): https://leetcode-cn.com/problems/binary-subarrays-with-sum/solution/930-he-xiang-tong-de-er-yuan-zi-shu-zu-javapython-/
[7]
【992. K 个不同整数的子数组】滑动窗口(Python): https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/992-k-ge-bu-tong-zheng-shu-de-zi-shu-zu-hua-dong-c/
[8]
【1004. 最大连续 1 的个数 III】滑动窗口(Python3): https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/1004-zui-da-lian-xu-1de-ge-shu-iii-hua-dong-chuang/
[9]
【1234. 替换子串得到平衡字符串】[Java/C++/Python] Sliding Window: https://leetcode.com/problems/replace-the-substring-for-balanced-string/discuss/408978/javacpython-sliding-window/367697
[10]
【1248. 统计「优美子数组」】滑动窗口(Python): https://leetcode-cn.com/problems/count-number-of-nice-subarrays/solution/1248-tong-ji-you-mei-zi-shu-zu-hua-dong-chuang-kou/