Python 滑动窗口算法实战：最小长度子数组

能跑通滑动窗口的题目，往往有个前提：数组里的数得是正整数。这样才具备单调性——往窗口里塞个数，总和肯定涨；挪走一个，总和肯定跌。有了这个性质，双指针才能稳稳当当干活。

一、209. 长度最小的子数组

这是滑动窗口最经典的练手题。题目给了一串正整数和一个目标值 target，让你找出一段连续子数组，它们的和至少是 target，而且长度要尽可能短。找不到就返回 0。

怎么想？

别急着写代码，先理清楚窗口的变化逻辑。 想象你手里拿着两个指针，left 和 right，中间夹着一个窗口。 right 负责探路，每走一步就把新数字加进总和 s 里。 一旦 s 够大了（≥ target），说明当前窗口已经达标。这时候别停，赶紧把 left 往右挪，看看能不能在保持达标的前提下把窗口缩得更小。 每缩一次，就记一下现在的长度，跟之前的最小值比一比，取小的那个。 一直缩到 s 又不够了，再让 right 继续探路。

这里有个坑：初始化最小长度时，别设成 0 或者无穷大随便填，最好设成 n + 1。这样最后判断一下有没有被更新过，就能知道到底存不存在解。

代码落地

from typing import List

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1
        s = left = 0
        
        for right, x in enumerate(nums):
            # 扩大窗口，累加当前元素
            s += x
            
            # 当窗口和满足条件时，尝试收缩左边界
            while s >= target:
                ans = min(ans, right - left + 1)
                s -= nums[left]
                left += 1
                    
        return ans if ans != n + 1 else 0

注意看那个 while 循环。很多人会误写成 if，那样只能找到第一个满足条件的窗口，而不是最短的。只有不断收缩直到不满足条件，才能保证对于当前的 right，找到了以它结尾的最短合法子数组。

跑一遍下来，每个元素最多被 right 访问一次，被 left 访问一次，所以时间复杂度是 O(n)。空间上只用了几个变量，O(1) 搞定。