Python 基础算法实战：滑动窗口详解

滑动窗口算法通常要求数组元素为正整数。这保证了当右指针向右移动时总和单调递增，左指针移动时总和单调递减，从而具备贪心性质。

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

思路解析

核心在于维护一个动态窗口 [left, right]。我们不断扩展右边界 right 累加数值，一旦窗口内和 sum 达到或超过 target，就尝试收缩左边界 left 来寻找更短的有效子数组。

这里有个细节要注意：ans 初始值设为 n + 1 或者无穷大，最后判断是否更新过。实际运行中，如果 nums 为空或没有满足条件的子数组，最终 ans 会保持初始的大值，此时返回 0 即可。

代码实现

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 else 0

这种写法时间复杂度是 O(n)，因为左右指针各遍历一次数组。相比暴力枚举的 O(n^2)，在数据量大时优势明显。注意初始化值和边界判断，确保逻辑闭环。