长度最小的子数组（LeetCode 209）

题目来源：LeetCode 209 · 长度最小的子数组

题目

给定一个正整数数组 nums 和目标值 target，找出和 ≥ target 的长度最小的连续子数组，返回其长度；不存在则返回 0。

思路：滑动窗口

抓住「全是正整数」这个约束：sum 随窗口变大而增大，随窗口变小而减小——这保证了指针只能单向移动，不会来回反复。

1. right 扩张窗口：每轮把 nums[right] 纳入窗口（sum 只增不减）
2. 窗口和 ≥ target 时，while 收缩窗口：记录当前长度、移出 nums[left]、left 前进
3. 收缩到 sum 再次 < target，停止收缩，right 继续扩张
4. 每个元素最多被 right 纳入一次、被 left 移出一次，总共 O(n)

for 只管扩张、while 只管收缩，窗口就像一条尺子滑过数组。

动画演示

代码

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    left, window_sum = 0, 0
    ans = float("inf")  # 哨兵：表示「尚未找到」
    for right in range(len(nums)):
        window_sum += nums[right]  # 扩张：纳入右侧元素
        while window_sum >= target:  # 达标，收缩左侧
            ans = min(ans, right - left + 1)
            window_sum -= nums[left]
            left += 1
        if ans == 1:  # 早退剪枝：1 已是最小可能长度
            return 1
    return 0 if ans == float("inf") else ans

三个特点

滑动窗口

本题解法依赖「数组全为正整数」：纳入元素只增 sum、移出只减 sum，所以两个指针都单向移动、不需要回头。若数组含负数，sum 可能变小也可能变大，这个单调性就不成立，题目会变成另一类问题。

哨兵

ans = float("inf") 表示「还没找到任何满足的子数组」。最后用 0 if ans == float("inf") else ans 区分两种情况：不存在（返回 0）与找到了（返回长度）。也可以用 ans = len(nums) + 1 做哨兵，效果相同——关键在于不能把「没找到」误当成长度为 0 的答案。

早退剪枝

长度最小只可能是 1（单元素 ≥ target 即成立）。所以一旦 ans == 1，不可能再更小，直接 return 1，省去后面所有扫描。最好情况下能提前跳出整个循环。

复杂度

• 时间：O(n)，每个元素最多被纳入和移出各一次
• 空间：O(1)，只有两个指针和一个 sum

边界情况

• 空数组：循环不进入，哨兵未被更新，返回 0
• 单元素恰好满足：ans = 1，早退剪枝直接返回
• 单元素不满足：sum < target，返回 0
• 整个数组和 < target：循环结束哨兵仍未被更新，返回 0
• 整个数组和恰好 = target：最后一次收缩更新 ans = len(nums)，返回 n