滑动窗口:窗子怎么伸缩

代码

def minSubArrayLen(target, nums):
    left = 0
    total = 0
    ans = float('inf')

    for right in range(len(nums)):
        total += nums[right]              # ① 右边先吃进来

        while total >= target:            # ② 满足了就往回缩
            ans = min(ans, right - left + 1)   # ③ 记录必须在缩之前
            total -= nums[left]
            left += 1

    return 0 if ans == float('inf') else ans

三个容易错的地方

① 为什么是 while,不是 if

右指针吃进一个大数之后,窗口可能一次能缩好几格还满足条件。 用 if 只缩一次,就会漏掉更短的答案。 把 target 拖到 3 试试:某些步会连着缩两次,那正是 while 在起作用。

② 为什么答案要在收缩之前记

进到 while 里面,说明此刻窗口是满足条件的。 一旦执行了 total -= nums[left],窗口就可能不再满足了—— 这时候再记长度,记的是个不合法的窗口。 求最短的题,一律「满足就记,记完再缩」。

③ 左指针为什么不会跑过右指针

因为数组元素都是正数,窗口缩到只剩一个元素时, total 就是 nums[right] 本身; 再缩一次 total 归零,必然小于 target,循环就退出了。 题目条件里的「正整数」不是废话——有负数这套就不成立,得换前缀和。

求最短 vs 求最长

同样是可变长窗口,这两类的收缩时机正好相反,别记混:

记法:缩的那一刻,窗口的合法性正在改变。 求最短是「从合法缩到不合法」,所以记录在前; 求最长是「从不合法缩回合法」,所以记录在后。