长度最小的子数组

🟡 Medium · 🏷️ 数组、滑动窗口、前缀和 · LeetCode#209

📖 题目

找出和 ≥ target 的最短连续子数组长度，不存在返回 0。

输入	输出	说明
target=7, nums=[2,3,1,2,4,3]	2	子数组 [4,3] 和为7，长度最短

💡 思路

连续子数组问题，用滑动窗口：维护一个窗口 [left, right]，右边界不断扩大，一旦窗口内的和达到了 target，就尝试收缩左边界看能不能更短——每次收缩前先记录一次当前窗口长度，因为不知道哪一步会是最短的答案。

不够 → 右边扩大
够了 → 记录长度，左边收缩

收缩时要注意顺序：先用 nums[left] 更新窗口和（把它减掉），再把 left 往右移一位——nums[left] 是即将被踢出窗口的元素，得先把它的贡献减掉。

💻 代码

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        window_sum = 0
        min_len = len(nums) + 1
        for right in range(len(nums)):
            window_sum += nums[right]          # 扩大
            while window_sum >= target:         # 够了就收缩
                min_len = min(min_len, right - left + 1)
                window_sum -= nums[left]
                left += 1
        return min_len if min_len <= len(nums) else 0

看起来是两层循环，但 left 总共最多移动 n 次（不会走回头路），所以时间复杂度仍是 O(n)，空间复杂度 O(1)。