Minimum Size Subarray Sum
给定一个正整数 target 和一个由正整数组成的数组 nums。请找出和至少为 target 的最短子数组（由相邻元素组成的一段），并返回它的长度。如果没有子数组的和达到 target，则返回 0。
函数
- targetinteger
- 子数组必须达到或超过的总和
- numsinteger-array
- 正整数数组
- 返回值integer
- 和至少为 target 的最短子数组的长度；如果不存在，则为 0
约束条件
1 ≤ target ≤ 1091 ≤ nums.length ≤ 2 × 1041 ≤ nums[i] ≤ 104
示例
- 输入
- target = 15nums = [4, 2, 9, 3, 7, 1, 5]
- 输出
- 3
- 解释
- 没有两个相邻数之和达到 15：最大的组合是 9 + 3 = 12。三个相邻数可以达到：4 + 2 + 9 = 15，9 + 3 + 7 = 19，所以答案是 3。
- 输入
- target = 11nums = [1, 2, 3, 4]
- 输出
- 0
- 解释
- 整个数组的总和是 10，小于 11，因此没有子数组达到目标值，答案是 0。
- 输入
- target = 8nums = [3, 8, 2]
- 输出
- 1
- 解释
- 值 8 单独就能达到目标，而且没有比一个元素更短的子数组。
进阶
如果 nums 也可能包含零和负数，导致滑动窗口不再适用，你会如何解决这个问题？
提示
逐个打开提示，每个都会多透露一点。
所有值都是正数。当你在右侧再添加一个元素，或从左侧移除一个元素时，子数组的和会发生什么变化？
保留一个窗口
nums[left..right]，并记录它的和。从右侧扩大窗口，直到和达到target。此时，这个窗口就是一个候选窗口，你可以尝试缩短它。当总和大于或等于
target时，记录窗口的长度，并移除nums[left]。左右两端都只会向右移动，因此每个元素只会进入和离开窗口各一次。
题解
每个值都是正数，因此扩展子数组会增大它的和，缩短子数组会减小它的和。所以，随着起点右移，最佳终点不会左移。只需让一个窗口右侧扩展、左侧收缩，就能一遍遍历找到答案。
从每个起点开始延伸
结果正确，但无法在最大的测试中运行完毕
思路
固定一个起点，然后向右累加值。运行总和第一次达到 target 时，你就得到了从该起点开始的最短子数组，因为更短的子数组总和都更小。记录它的长度，然后移到下一个起点；所有起点中最小的长度就是答案。
如果没有子数组达到目标，每个起点都要一直遍历到数组末尾：需要进行 n(n+1)/2 次加法，当 n = 2 × 10^4 时，大约是 2 × 10^8 次。
算法
- 将
best设为 0，表示还没有找到结果。 - 对于每个起始索引，将当前总和设为 0。
- 从起始位置向右移动结束索引，并将
nums[end]加到总和中。 - 当总和达到
target时，如果end-start+1比best更优，就保留它，然后停止扩展这个起始位置。 - 返回
best。
def minSubArrayLen(target, nums):
n = len(nums)
best = 0 # 0 means no subarray found yet
for start in range(n):
total = 0
for end in range(start, n):
total += nums[end]
if total >= target:
# The shortest subarray from this start ends here
if best == 0 or end - start + 1 < best:
best = end - start + 1
break
return best前缀和与二分查找
思路
令 prefix[k] 表示前 k 个值的和，其中 prefix[0] = 0。nums[start..end-1] 的和是 prefix[end] - prefix[start]，因此，对于固定的起点，你要找到满足 prefix[end] ≥ prefix[start] + target 的最小 end。由于所有值都是正数，prefix 会严格递增，因此可以通过二分查找找到这个终点。
在第一个示例中，prefix 是 [0, 4, 6, 15, 18, 25, 26, 31]。从起点 2 开始，你需要 6 + 15 = 21；第一个大于或等于 21 的前缀值是索引 5 处的 25，因此窗口中的值是 9、3、7，长度为 3。
如果 prefix[n] 小于某个起点所需的值，那么之后的起点也都无法满足条件，因此你可以停止。总共需要进行 n 次二分查找，时间复杂度为 O(n log n)，空间复杂度为 O(n)。
算法
- 构建长度为
n+1的prefix，其中prefix[k+1] = prefix[k] + nums[k]。 - 对于每个起始位置，计算
need = prefix[start] + target。 - 如果
prefix[n] < need，就停止：之后的起始位置都无法成功。 - 在位置
start+1到n之间进行二分查找，找到第一个满足prefix[end] ≥ need的end，如果end-start是目前最短的长度，就保留它。 - 返回最短长度；如果没有任何起始位置成功，则返回 0。
from bisect import bisect_left
def minSubArrayLen(target, nums):
n = len(nums)
# prefix[k] is the sum of the first k values; it only grows
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
best = 0
for start in range(n):
need = prefix[start] + target
if prefix[n] < need:
break # no window from here on can reach target
# The first end with prefix[end] >= need closes the shortest window
end = bisect_left(prefix, need, start + 1)
if best == 0 or end - start < best:
best = end - start
return best滑动窗口
思路
永久舍弃一个起始位置是安全的。当窗口 nums[left..right] 首次达到 target 时，以 right-1 结尾的窗口尚未达到目标，否则循环早一步就会缩小窗口。因此，right 是这个起始位置对应的最早结束位置，之后的结束位置只会得到更长的子数组。记录长度，舍弃 nums[left]，并在总和仍达到 target 时继续缩小窗口。
在第一个示例中，总和依次增至 4、6、15：记录 3 并舍弃 4。加上 3 和 7 后总和变为 21：记录 4，舍弃 2（总和变为 19），记录 3，舍弃 9（总和变为 10）。之后没有更短的结果。
每个索引只进入窗口一次，也只离开窗口一次，因此嵌套循环总共执行 O(n) 次操作，空间复杂度为 O(1)。
算法
- 将
left = 0、total = 0和best = 0设为初始值。 - 对于每个
right，将nums[right]加到total中。 - 当
total ≥ target时，如果right-left+1大于best，就将其保存为best；然后减去nums[left]，并将left向右移动一步。 - 返回
best。如果总和始终没有达到target，它仍为 0。
def minSubArrayLen(target, nums):
best = 0 # 0 means no window found yet
total = 0 # sum of nums[left .. right]
left = 0
for right in range(len(nums)):
total += nums[right]
# Shrink while the window still reaches target
while total >= target:
if best == 0 or right - left + 1 < best:
best = right - left + 1
total -= nums[left]
left += 1
return best
易错点和边界情况
- 用
if而不是while缩小窗口。对于target = 12和[1, 1, 2, 3, 12]，加上 12 后总和为 19；if会记录长度 5，移除一个值后继续，因此永远不会测量窗口[12]。 - 在移除
nums[left]后记录长度。你必须测量总和达到target的窗口。 - 用
>而不是≥进行比较。对于target = 9，[3, 3, 3]的答案是 3，而不是 0。 - 返回哨兵值。如果
best从n+1或无穷大开始，当没有任何窗口达到target时，就返回 0，就像第二个示例中那样。
常见问题4
最小长度子数组和的时间复杂度是多少？
滑动窗口的时间复杂度为 O(n)，空间复杂度为 O(1)。内层循环看起来是二次复杂度，但 left 只会向前移动，所以在整个运行过程中最多移动 n 次。前缀和版本的时间复杂度为 O(n log n)，而尝试每个起点的时间复杂度为 O(n²)。
为什么滑动窗口需要正数？
只有当窗口的总和达到 target 时，窗口才会缩小，因为此时移除一个值只会让总和降低。遇到负数时，移除它反而会让总和升高。对于 [5, -10, 20] 和 target = 15，窗口会停在 -10, 20，总和为 10，因此始终不会测量 [20]，长度为 1。
既然存在 O(n) 的解法，为什么还要学习 O(n log n) 的前缀和解法？
面试官常会在得到 O(n) 的答案后继续问这个问题。它以另一种方式利用了正数这一条件：前缀和是有序的，因此可以通过二分查找找到累计总和首次超过阈值的位置。同样的方法还能按权重比例随机选取一个索引。
子数组的和必须正好等于 target 吗？
不对。任何大于或等于 target 的总和都算。对于 target = 15，窗口中的 9、3、7 相加为 19，长度仍为 3。
def minSubArrayLen(target, nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
target = 15 nums = [4, 2, 9, 3, 7, 1, 5]
预期输出
3