Skip to main content

滑动窗口

什么是滑动窗口​

滑动窗口是双指针的其中一种，它使用两个（或以上）移动方向相同的指针在可遍历对象（例如数组或字符串）中寻找最长（最短）的合法子区间。

课前练习​

尝试先完成以下课前练习，并且阅读官方题解：

什么时候使用滑动窗口​

滑动窗口分为固定长度以及非固定长度两种：

  • 固定长度：左右指针的距离固定
  • 非固定长度：左右指针距离不固定

固定长度的题目相对比较简单，本文内容主要针对非固定长度的题目，滑动窗口的题目通常要求从所有可能的子区间中找到一个的合法子区间，例如在 3. 无重复字符的最长子串中，题目要求从所有可能的子串中找到一个最长的没有包含重复字符的子串。找所有可能的子串可以通过遍历左边界，找到所有可能的右边界对，伪代码如下：

for left in strings.length
    for right in left + 1 to strings.length
        sub.append(left, right)

为了方便分析，本文使用了遍历右边界的方式：

for right in strings.length
    for left in 0 to right - 1
        sub.append(left, right)

给定字符串 S = "vacdaf"，以上的暴力解尝试检查以每个字符为右边界的所有子串，在这个例子中，子串数量分别为 1, 2, 3, 4, 5。

range

假设字符串长度为 N，即总子串数量为 1 + 2 + 3 .... + N-1 = N^2，若检查每个子串是否合法需要的时间为 O(S)，那么暴力解的时间复杂度为 O(N^2*S)。数组或字符串的题目通常有多种解法，通过以下几种优化方案，可以减少检查的子区间数量，从而减少算法的时间复杂度。

op

在字符串 S = "vacdaf" 中，当右边界索引为 4，左边界索引为 1 的时候，a 出现了两次，所以 S[1:5] 为不符合要求的字符串。根据这个信息，我们可以得出：

  • 对于任意包含 S[1:5] 的子串，即 S[0:6], S[1:6] 都不可能符合要求，可以跳过检查。
  • 从而对于任意 V 大于 4，S[0:V], S[1:V] 都不可能符合要求。

我们可以使用左指针来标记合法子串的左边界起始索引 2，减少需要检查的子串数量。

range2

一般来说，当随着右边界的增加，左指针单调不减的时候，可以考虑滑动窗口。上述例子中，对于每个字符的右边界和左边界分别为：

[0,1,2,3,4,5]
[0,0,0,0,2,2]

与此相反，1124. 表现良好的最长时间段并不符合这个条件，例如当数组为 [6,9,9,6] 的时候，对于每个字符的右边界和左边界分别为：

[0,1,2,3]
[0,1,0,1]

可以看到左指针并非单调不减。

解题模式​

由于固定右边界的情况下，左指针不断右移，子区间的长度不断减少。我们可以推断出滑动窗口的解题流程如下：

flow

最长合法子区间：对于每个右边界，通过左指针的右移来找到第一个合法子区间必定是最长的合法子区间。以下为寻找最长合法子区间的伪代码：

longest_valid(strings):
    res = 0
    left = 0
    for i = 0 to strings.length
        add strings[i] to state
        while state is not valid
            // 通过左指针右移来寻找第一个合法子区间
            remove strings[left] in state
            left++
        // i 的第一个合法子区间
        res = max(res, i - left + 1)
    return res

3. 无重复字符的最长子串 的伪代码：

lengthOfLongestSubstring(strings)
    res = 0
    left = 0
    count = HashMap[(string, int)]
    for i = 0 to strings.length
        count[strings[i]] += 1
        while count[strings[i]] > 1
            count[strings[left]] -=1 
            left ++
        res = max(res, i - left + 1)
    return res

最短合法子区间：对于每个右边界，通过左指针的右移来找到的最后一个合法子区间必定是最短的合法子区间。以下为寻找最短合法子区间的伪代码：

shortest_valid(strings):
    res = len(strings) + 1
    left = 0
    for i = 0 to strings.length
        add strings[i] to state
        while state is valid
            // 更新 res，直到最后一个合法子区间
            res = min(res, right - left + 1)
            remove strings[left] in state
            left++
    return res

209. 长度最小的子数组 的伪代码：

minSubArrayLen(target, nums):
    res = nums.length + 1
    left = cur = 0
    for i = 0 to nums.length:
        cur += nums[i]
        while cur >= target:
            res = min(res, i - left + 1)
            cur -= nums[left]
            left ++
    return 0 if res == nums.length + 1 else res

检查代码​

按照这两个 API 来编写代码的话，并不容易犯错，注意大部分时候 left 指针不能大于等于 right 指针，这点隐含在 state 的校验中。

课后练习​