滑动窗口算法通常要求数组元素为正整数。这保证了当右指针向右移动时总和单调递增,左指针移动时总和单调递减,从而具备贪心性质。
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),在数据量大时优势明显。注意初始化值和边界判断,确保逻辑闭环。


