209. 长度最小的子数组

题目

力扣题目

给定一个含有 n 个正整数的数组 nums 和一个正整数 target。

找出该数组中满足元素总和大于等于 target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

进阶：在 $O(n)$ 的滑动窗口解法之外，还可以尝试使用前缀和与二分查找实现 $O(n\log n)$ 的解法。

考察内容

• 连续子数组与区间和
• 滑动窗口的扩张和收缩
• 快慢指针
• 单调性对算法成立条件的影响
• 暴力枚举与线性算法的复杂度比较

解题思路

暴力枚举

固定子数组左端点 i，然后不断向右累加。第一次出现 sum >= target 时，当前右端点已经给出了以 i 开头的最短合法子数组，记录长度后即可停止这一轮。

因为需要枚举所有左端点，并在最坏情况下继续枚举右端点，所以：

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

滑动窗口

使用 [left, right] 表示当前窗口，sum 保存窗口内所有元素之和：

1. 移动 right，将 nums[right] 加入窗口；
2. 当 sum >= target 时，当前窗口已经合法，记录窗口长度；
3. 持续移动 left 并减去离开窗口的元素，寻找以当前 right 结尾的最短合法窗口；
4. 当 sum < target 后，再继续扩张右边界。

这里必须使用 while (sum >= target)，而不是 if。一个窗口满足条件后，可能还能连续删除多个左侧元素并保持合法；只有持续收缩，才能得到最短长度。

循环过程中可以维护以下不变量：

• sum 始终等于当前窗口 [left, right] 的元素和；
• 内层循环结束后，当前窗口满足 sum < target，已经不能继续收缩；
• result 保存目前见过的所有合法窗口中的最短长度。

本题中所有 nums[i] 都是正数，因此：

• 右边界向右移动时，窗口和只会增大；
• 左边界向右移动时，窗口和只会减小。

正是这种单调性保证了滑动窗口解法正确。如果数组中允许出现负数，简单滑动窗口就可能漏掉答案。

以 target = 7、nums = [2,3,1,2,4,3] 为例：

两个指针都只会从左向右移动一次，因此：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

前缀和 + 二分查找

因为数组元素均为正数，前缀和数组严格递增。对于每个左端点 i，可以二分查找第一个满足：

的位置 j，并用 j - i 更新答案。构造前缀和需要 $O(n)$，进行 n 次二分查找需要 $O(n\log n)$，额外空间复杂度为 $O(n)$。

代码演示

// 暴力双循环 肯定会超时
int minSubArrayLen(int target, std::vector<int>& nums) {
    int n      = nums.size();
    int result = INT_MAX;
    for (int i = 0; i < n; ++i) {
        int sum = 0;
        for (int j = i; j < n; ++j) {
            sum += nums[j];
            if (sum >= target) {
                result = std::min(result, j - i + 1);
                break;
            }
        }
    }
    return result == INT_MAX ? 0 : result;
}

// 双指针
int minSubArrayLen2(int target, std::vector<int>& nums) {
    int n      = nums.size();
    int result = INT_MAX;
    int64_t sum    = 0;
    int left = 0, right = 0;
    while (right < n) {
        sum += nums[right];
        while (sum >= target) {
            result = std::min(result, right - left + 1);
            sum -= nums[left];
            ++left;
        }
        ++right;
    }
    return result == INT_MAX ? 0 : result;
}

易错点

• 把子数组理解成子序列：子数组必须连续，不能跳过中间元素。
• 内层收缩使用 if：合法窗口可能连续收缩多次，必须使用 while (sum >= target)。
• 先减去左端元素再更新答案：应该先记录当前合法窗口长度，再移动左边界。
• 漏掉新加入的右端元素：每轮外层循环应先执行 sum += nums[right]，然后尝试收缩。
• 窗口长度少算或多算一位：闭区间 [left, right] 的长度是 right - left + 1。
• 不存在答案时返回 INT_MAX：应按照题目要求返回 0。
• 忽略正整数条件：简单滑动窗口依赖窗口和的单调变化，不能直接推广到包含负数的数组。
• 累加和可能溢出：当前代码使用 int64_t sum，能够安全覆盖题目给出的数据范围。

总结

本题是滑动窗口的经典模型：

• 当窗口和不足时，移动 right 扩张窗口；
• 当窗口和达到目标时，移动 left 收缩窗口并更新最短长度；
• 每个元素最多进入和离开窗口一次，因此总时间复杂度为 $O(n)$。

真正需要记住的不是模板本身，而是滑动窗口成立的原因：所有元素都是正数，扩张和收缩会让窗口和产生确定的单调变化。

相关题目

• 3. 无重复字符的最长子串
• 76. 最小覆盖子串
• 904. 水果成篮
• 1004. 最大连续 1 的个数 III
• 713. 乘积小于 K 的子数组
• 862. 和至少为 K 的最短子数组