LeetCode 209 - 长度最小的子数组（Minimum Size Subarray Sum）

算法刷题>LeetCode>面试经典150
3.1k words

LeetCode 209 - 长度最小的子数组

问题描述

给定一个含有 n 个正整数的数组 nums 和一个正整数 target，找出总和大于等于 target 的最短连续子数组 [l..r] 并返回其长度；若不存在，返回 0。

示例

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 满足条件且长度最短。

示例 2：

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

约束

  • 1 <= target <= 1e9
  • 1 <= nums.length <= 1e5
  • 1 <= nums[i] <= 1e4

由于元素均为正数，可用单调移动的滑动窗口；也可以用前缀和 + 二分实现 O(n log n)。

解题思路

方法一：滑动窗口（双指针，O(n)）

关键洞见：nums[i] > 0，右指针右移使窗口和单调不减；当窗口和 >= target 时，左指针尽量右移缩小窗口。

算法步骤：

  1. 维护窗口 [left, right] 及窗口和 windowSum。
  2. 右指针向右扩张，加上 nums[right]。
  3. 当 windowSum >= target 时，不断右移 left 缩小窗口并更新最短长度。
  4. 遍历结束返回答案，若未更新则为 0。

边界与细节：

  • 因为均为正数，缩窗不会错过最优解；
  • 使用 Integer.MAX_VALUE 记录答案初值；
  • 注意返回 0 的情形。

为什么缩窗是安全的（正确性要点）

  • 不变式：每一步都维护当前窗口和 windowSum = sum(nums[left..right])，且窗口始终合法（left <= right + 1）。
  • 单调性：元素为正 ⇒ 当右移 right 时，windowSum 非减；当右移 left 时，windowSum 严格减。
  • 决策准则：一旦 windowSum >= target，继续扩大窗口只会使长度更大，故应尽量右移 left 缩短长度，直到再次小于 target 为止。此过程不会跳过任何更短可行解，因为任何包含更靠左元素的窗口都不可能更短。

手把手执行示例（target = 7, nums = [2,3,1,2,4,3]）

记法：[left..right] 为当前窗口，ans 为最短长度。

step right 加入 window 前 window 后 缩窗动作 ans 更新
1 +2 [] sum=0 [0..0] sum=2 无 -
2 +3 [0..0] 2 [0..1] 5 无 -
3 +1 [0..1] 5 [0..2] 6 无 -
4 +2 [0..2] 6 [0..3] 8 sum>=7，缩窗：去掉2 → [1..3] sum=6 ans=3 (len=4→缩后3)
5 +4 [1..3] 6 [1..4] 10 sum>=7，缩窗：去掉3 → [2..4] 7 → ans=min(3,3)=3，继续缩：去掉1 → [3..4] 6 ans 仍为 3
6 +3 [3..4] 6 [3..5] 9 sum>=7，缩窗：去掉2 → [4..5] 7 → ans=min(3,2)=2，继续缩：去掉4 → [5..5] 3 ans=2

最终答案为 2，对应窗口 [4,3]（索引 [4..5]）。可以看到，每次达到阈值后尽可能缩窗，能及时发现更短长度。

常见陷阱与排错

  • 忘记在 while (windowSum >= target) 内更新 ans 再缩窗，可能错过更短长度。
  • 将 while 写成 if，会少做多次缩窗，得到非最优长度。
  • 误用负数或零元素时的滑动窗口模板。本题依赖“正数”保证单调性，若允许负数，需要改用前缀和 + 有序结构的思路。

方法二：前缀和 + 二分（O(n log n)）

构造前缀和 pre[i] 表示前 i 个元素之和，pre[0]=0。对每个 i，我们希望找到最小的 j < i 使得 pre[i] - pre[j] >= target，等价于 pre[j] <= pre[i] - target。由于前缀和严格递增（元素均为正），可对 pre 做二分查找满足条件的最右 j。

实现要点：

  • 维护长度为 n+1 的前缀和数组；
  • 对每个 i，在 pre[0..i] 上二分 pre[i] - target 的上界位置；
  • 取最短长度 i - j 更新答案。

代码实现

Java - 滑动窗口（O(n)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int left = 0;
    int windowSum = 0;
    int answer = Integer.MAX_VALUE;

    for (int right = 0; right < n; right++) {
        windowSum += nums[right];
        while (windowSum >= target) {
            answer = Math.min(answer, right - left + 1);
            windowSum -= nums[left++];
        }
    }

    return answer == Integer.MAX_VALUE ? 0 : answer;
}

Java - 前缀和 + 二分（O(n log n)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int minSubArrayLenBinary(int target, int[] nums) {
    int n = nums.length;
    long[] pre = new long[n + 1];
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + nums[i - 1];
    }

    int answer = Integer.MAX_VALUE;
    for (int i = 1; i <= n; i++) {
        long need = pre[i] - target; // 寻找最大的 j 使 pre[j] <= need
        int j = upperBound(pre, 0, i, need) - 1; // 上界-1 即为满足条件的最右 j
        if (j >= 0) {
            answer = Math.min(answer, i - j);
        }
    }

    return answer == Integer.MAX_VALUE ? 0 : answer;
}

// 返回在 pre[l..r) 中第一个 > x 的下标
private int upperBound(long[] pre, int l, int r, long x) {
    int left = l, right = r; // [left, right)
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (pre[mid] <= x) left = mid + 1; else right = mid;
    }
    return left;
}

方法比较

方面 滑动窗口 前缀和 + 二分
时间复杂度 $O(n)$ $O(n \log n)$
空间复杂度 $O(1)$ $O(n)$
适用前提 元素为正 元素为正
实现难度 低 中

复杂度分析

  • 滑动窗口：每个元素最多进出窗口一次，总时间 $O(n)$，常数额外空间 $O(1)$。
  • 前缀和 + 二分：构建前缀和 $O(n)$，每个位置一次二分 $O(\log n)$，总 $O(n\log n)$，空间 $O(n)$。

关键收获

  • 元素全为正数是滑动窗口正确性的根本保障；
  • 二分法依赖前缀和的单调性，注意使用上界定位最右可行 j；
  • 面对“最短/最小长度的连续子数组且和有下界”的问题，优先考虑滑动窗口。