滑动窗口法

所需变量

滑动窗口由三部分构成：边界，条件相关变量，需求记录变量。

边界

边界由两个指针构成，分别称为左边界和右边界。

条件相关变量

条件相关变量是用于存储题目所需条件数值的变量。（例如区间和，区间长）

需求记录变量

需求记录变量是用于算法计划返回的变量，也是题目需求的变量，通常是最大值或最小值（例如区间和最大值，或是满足条件的区间最长长度）

方法步骤

听好了，我只写一遍。

  1. 所需变量声明
  2. 进行循环，在循环中不断移动右边界，同时不断更新条件相关变量
  3. 在每次移动右边界后，检查条件相关变量是否满足需求记录变量，如果满足则进入另一个循环。
  4. 在另一个循环中，左边界不断移动，更新条件相关变量，记录需求记录变量，直到条件相关变量不满足条件，循环破坏，回到右边界移动的大循环
  5. 需求记录变量为所求
  6. 去跟小伙伴们吹逼

更加易懂的代码版本（也就是模板代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def sumWindow(nums: List[int]) -> nums:
    # 窗口左右边界
    left = 0
    right = 0
    # 条件相关变量
    sum = 0     # 以窗口内元素总和为示例
    res = 0     # 以求最大元素总和为例

    # 遍历
    while right < len(nums):
        # 更新值
        sum += nums[right]

        # 如果满足条件，则左边界移动，遍历并记录，直至破坏条件
        while sum > target:
            # 记录最大值
            res = max(sum,res)
            # 左边界移动，更新 sum
            sum -= nums[left]
            left += 1

        # 右边界移动
        right += 1

    return res      # 别高兴到忘了返回...

论为什么滑动窗口比暴力快

猜测上，滑动窗口采用了一种特别的遍历方法，能够在有效排除不符合条件的组合的同时不排除满足条件的组合。

由于满足条件的数组之间存在有一定相似性，滑动窗口法通过利用这个相似性——在两端移动过程中处于满足条件和不满足条件之间反复横跳，以高效遍历所有可能的组合。

经典为例

长度最小的子数组

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

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

显然可以使用暴力解法，但是本文在此不做提及。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 滑动窗口法
        left = 0    # 左边界
        right = 0   # 右边界
        sum = 0     # 条件相关变量（区间和）
        ret = 0     # 需求记录变量（区间和最大值）
        length = len(nums)

        while right < length:
            # 稳定往窗口加数
            # 右边界无条件移动，并且移动时计算当前的条件相关变量值
            sum += nums[right]
            right += 1

            # 满足题目条件记录下来，然后 持续 往窗口减数
            # 仅在条件相关变量满足条件时执行，左边界移动，破坏满足的条件，并记录需求记录变量
            while sum >= target:
                # 记录
                if ret == 0:
                    ret = right - left
                else:
                    ret = min(ret, right - left)
                
                # 减数
                sum -= nums[left]
                left += 1
        
        return ret