给定一个含有 正整数 的数组 nums 和一个正整数 target。
找出总和 ≥ target 的 长度最小 的连续子数组,并返回其长度。若不存在返回 0。
约束: 1 ≤ target ≤ 1e9, 1 ≤ nums.length ≤ 1e5, 1 ≤ nums[i] ≤ 1e4
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
触发信号:连续子数组 + 正数 + 总和/乘积条件
核心不变量:窗口 [left, right] 内总和 < target 时,right 右移;≥ target 时收缩 left。
复杂度:时间 O(n) | 空间 O(1)
常见错误:忘记正数条件导致窗口不可收缩;更新 ans 时机错误。
迁移:乘积小于K的子数组、最短包含字符子串。
改编:给定正整数数组,返回总和 < target 的连续子数组的个数(不是最短长度)。
提示:滑动窗口计数,每次 right 移动后,以 right 结尾的合法子数组数为 left 到 right 的长度。
def countSubArrays(nums, target):
left = 0; cur = 0; ans = 0
for right, v in enumerate(nums):
cur += v
while cur >= target:
cur -= nums[left]
left += 1
ans += right - left + 1
return ans