Minimum Size Subarray Sum

求和至少为 target 的最短子数组长度。

求和至少为 target 的最短连续子数组长度。因为数组元素都是正数，所以一旦窗口和达到 target，就应该立刻尝试收缩。

ArraySliding Window

题目定位

因为数组元素为正，一旦当前和达到 target，想继续变短就只能收缩左边界，这是典型正数滑窗。

关键观察

正数保证了窗口和随指针移动具有单调性，这也是为什么这里滑窗比前缀和方案更自然。

目标复杂度

O(n) / O(1)

这题的解法思路怎么拆

维护当前窗口的区间和。

右指针不断扩张，直到窗口和达到或超过 target。

只要窗口仍然合法，就更新答案并持续收缩左边界。

正数条件正是这套逻辑成立的原因。

拿一个例子顺一遍

例如 target = 7, nums = [2, 3, 1, 2, 4, 3]。

扩到 [2, 3, 1, 2] 时，sum = 8，因此答案先变成 4。

继续收缩左边界得到 [3, 1, 2]，sum = 6，窗口失效。

后面当 [4, 3] 出现时，答案进一步缩短为 2。

参考实现

Python

def minSubArrayLen(target: int, nums: list[int]) -> int:
    left = 0
    window_sum = 0
    best = float("inf")

    for right, value in enumerate(nums):
        window_sum += value

        while window_sum >= target:
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return 0 if best == float("inf") else best

TypeScript 版本

TypeScript

function minSubArrayLen(target: number, nums: number[]): number {
  let left = 0;
  let windowSum = 0;
  let best = Number.POSITIVE_INFINITY;

  for (let right = 0; right < nums.length; right += 1) {
    windowSum += nums[right];

    while (windowSum >= target) {
      best = Math.min(best, right - left + 1);
      windowSum -= nums[left];
      left += 1;
    }
  }

  return Number.isFinite(best) ? best : 0;
}