长度最小的子数组
Minimum Size Subarray Sum
本机进度仅保存在当前浏览器
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足「和 ≥ target」的长度最小的连续子数组，并返回其长度；不存在则返回 0。
示例：target = 7，nums = [2, 3, 1, 2, 4, 3]，子数组 [4, 3] 最短，输出 2。
解题思路
- 元素全为正数，窗口和具有单调性：右扩必增、左缩必减，滑动窗口适用。
- 右指针不断扩张累加；当窗口和 ≥ target 时，尽量收缩左指针，用最短窗口长度更新答案。
- 每个元素最多进出窗口各一次，总时间 O(n)。
- 若数组含负数则单调性破坏，需改用前缀和 + 单调队列或二分，注意适用条件。
参考实现
查看参考实现Python · 建议先自行作答
def minSubArrayLen(target, nums):
# 窗口和 >= target 时收缩左端，取最短长度
l = 0
total = 0
best = len(nums) + 1
for r, x in enumerate(nums):
total += x
while total >= target:
best = min(best, r - l + 1)
total -= nums[l]
l += 1
return 0 if best > len(nums) else best