长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足和大于等于 target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

题目描述

示例：

Text
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 的和为 7，长度为 2，是满足条件的最短连续子数组。

提示：

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

题目关键条件

数组元素都是正整数。滑动窗口能在本题中成立，正是因为窗口右扩时 sum 只会增加，窗口左缩时 sum 只会减少。

如果数组中存在负数，这个单调性会被破坏，就不能直接套用本题这种滑动窗口写法。

解法一：暴力枚举

最朴素的做法是枚举每一个起点 i，然后继续枚举终点 j，不断累加 nums[i] + ... + nums[j]。

一旦当前区间和大于等于 target，就更新答案，并停止当前起点的继续枚举，因为再往后加只会让区间更长。

暴力枚举
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = INT_MAX;

        for (int i = 0; i < nums.size(); i++) {
            int sum = 0;
            for (int j = i; j < nums.size(); j++) {
                sum += nums[j];
                if (sum >= target) {
                    ans = min(ans, j - i + 1);
                    break;
                }
            }
        }

        return ans == INT_MAX ? 0 : ans;
    }
};

复杂度分析：

指标	复杂度	说明
时间复杂度	$O(n^2)$	最坏情况下每个起点都要向后扫描
空间复杂度	$O(1)$	只使用常数变量

当 nums.length 达到 $10^5$ 时， $O(n^2)$ 会超时。

解法二：滑动窗口

滑动窗口可以理解为数组上的一段连续区间 [left, right]。

本题窗口的含义是：当前正在考察的连续子数组。

窗口移动规则：

问题	回答
窗口内是什么？	一个连续子数组 `nums[left..right]`
右边界如何移动？	`right` 从左到右遍历数组，把新元素加入窗口
左边界如何移动？	当 `sum >= target` 时，尝试收缩左边界，看看能不能得到更短答案

配图 TODO

这里建议补一张图：用两个指针框出窗口 [left, right]，右指针不断扩张窗口；当窗口和达到 target 后，左指针不断右移收缩窗口，并在每次收缩前更新最短长度。

滑动窗口为什么正确

因为数组元素全为正数，所以：

右边界右移，窗口和一定变大或不变；
左边界右移，窗口和一定变小或不变。

因此，当当前窗口和已经满足 sum >= target 时，继续右扩只会让窗口更长，不可能得到以当前 right 结尾的更短答案。

这时应该不断移动 left，尝试缩小窗口，直到窗口不再满足条件。

滑动窗口
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = INT_MAX;
        int sum = 0;
        int left = 0;

        for (int right = 0; right < nums.size(); right++) {
            sum += nums[right];

            while (sum >= target) {
                ans = min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

        return ans == INT_MAX ? 0 : ans;
    }
};

复杂度分析：

指标	复杂度	说明
时间复杂度	$O(n)$	每个元素最多进入窗口一次、离开窗口一次
空间复杂度	$O(1)$	只使用常数变量

为什么 for 里面套 while 仍然是

O(n)

？

不要只看循环嵌套形式，要看每个元素被操作的次数。

right 从左到右走一遍，每个元素最多被加入窗口一次；left 也只会从左到右走一遍，每个元素最多被移出窗口一次。所以总操作次数是线性的。

手动模拟

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

步骤	操作	窗口	`sum`	是否更新答案
1	加入 `2`	`[2]`	2	否
2	加入 `3`	`[2,3]`	5	否
3	加入 `1`	`[2,3,1]`	6	否
4	加入 `2`	`[2,3,1,2]`	8	更新为 4，然后左缩
5	移出 `2`	`[3,1,2]`	6	停止收缩
6	加入 `4`	`[3,1,2,4]`	10	更新为 4，继续左缩
7	移出 `3`	`[1,2,4]`	7	更新为 3，继续左缩
8	移出 `1`	`[2,4]`	6	停止收缩
9	加入 `3`	`[2,4,3]`	9	更新为 3，继续左缩
10	移出 `2`	`[4,3]`	7	更新为 2，继续左缩
11	移出 `4`	`[3]`	3	停止收缩

最终答案是 2。

易错点

while (sum >= target) 不能写成 if。因为一个右边界固定时，左边界可能需要连续收缩多次。
更新答案要放在移出左端元素之前，因为当前窗口此时仍然满足条件。
不存在答案时，返回 0，所以通常用 INT_MAX 或 Infinity 作为初始值。
本题是连续子数组，不是子序列，不能跳着选元素。
滑动窗口依赖正整数条件，不能无脑迁移到含负数的区间和问题。

代码模板

C++
Java
Python
JavaScript
TypeScript

C++
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = INT_MAX;
        int sum = 0;
        int left = 0;

        for (int right = 0; right < nums.size(); right++) {
            sum += nums[right];

            while (sum >= target) {
                ans = min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

        return ans == INT_MAX ? 0 : ans;
    }
};

Java
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];

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

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

Python
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        ans = float('inf')
        total = 0
        left = 0

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

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

        return 0 if ans == float('inf') else ans

JavaScript
var minSubArrayLen = function(target, nums) {
    let ans = Infinity;
    let sum = 0;
    let left = 0;

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

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

    return ans === Infinity ? 0 : ans;
};

TypeScript
function minSubArrayLen(target: number, nums: number[]): number {
    let ans = Infinity;
    let sum = 0;
    let left = 0;

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

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

    return ans === Infinity ? 0 : ans;
}

总结

这道题是滑动窗口的经典入门题。

暴力解法枚举所有连续区间，时间复杂度是 $O(n^2)$ 。滑动窗口利用“数组元素均为正数”的单调性，让右指针负责扩张窗口，左指针负责在满足条件时收缩窗口，从而把复杂度优化到 $O(n)$ 。

题目描述​

解法一：暴力枚举​

解法二：滑动窗口​

滑动窗口为什么正确​

手动模拟​

易错点​

代码模板​

总结​