209. 长度最小的子数组

题目

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

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 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^5

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解答

思路

以 target = 7, nums = [2,3,1,2,4,3] 为例。首先考虑 暴力做法，我们依次枚举左端点 2->3->1...->3，对于每个左端点我们向右拓展直到当前连续子数组的和大于 7，记录下它的长度。比较 每个左端点得到的长度，将其中的最小值输出既可。

时间复杂度为 $O (n^{2}) \approx 10^{10}$ ，会超时。

换一种思路：枚举右端点。我们首先从 2 开始，发现 2, 3, 1, 2 刚好超过 target，因此 nums[3] = 2 对应的长度就是 4，从这个位置开始枚举右端点，由于 nums 都是正数，因此每次右端点加入连续子数组后，它的和一定超过 target，于是此时可以向右移动左端点，直到连续子数组刚好不符合要求为止：

nums[4] = 4，连续子数组为 [1, 2, 4]，前面的 [2, 3] 都被排除
nums[5] = 3，连续子数组为 [4, 3]，前面的 [1, 2] 都被排除
因此最短长度为 min(4, 3, 2) = 2

枚举右端点，收缩左端点 只枚举了右端点一遍，同时每个左端点都会收缩，因此：

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

代码

C++ 代码

cpp

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ans = INT_MAX;
        int sum = 0;

        int left = 0;
        int right = 0;

        for (; right < n; right ++) {
            sum += nums[right];

            while (sum - nums[left] >= target) {
                sum -= nums[left];
                left ++;
            }

            if (sum >= target) {
                ans = min(ans, right - left + 1);
            }
        }

        if (ans <= n) {
            return ans;
        }
        
        // ans <= n ? ans : 0;

        return 0;
    }
};

Python 代码

python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1
        s = 0
        left = 0

        for right, x in enumerate(nums):
            s += x
            
            # left = right --> s == 0
            while s - nums[left] >= target:
                s -= nums[left]
                left += 1
            
            if s >= target:
                ans = min(ans, right - left + 1)
        
        return ans if ans <= n else 0

小技巧：只有 sum - nums[left] > target 也就是即使删除左端点后，连续数组的和依然 > target 才将左端点删掉。

或者另一种写法：

Python 代码

python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1
        s = 0
        left = 0

        for right, x in enumerate(nums):
            s += x

            while s >= target:
                ans = min(ans, right - left + 1)
                s -= nums[left]
                left += 1
        
        return ans if ans <= n else 0

这种写法只有 s >= target 的时候更新 ans，虽然有可能 s -= nums[left] 之后导致 s < target（比如新加入的右端点比左端点小很多的情况）但是新加入一个，再删除一个，总长度并不会比上一个 ans 更小，因此等价于跳过这次循环。

虽然看上去像是 二重循环，但是由于 right 是从 0..n - 1，同时 left 每层循环也会 += 1。因此其实就是两次一重循环，时间复杂度为 $O (2 n)$ 。

同向双指针的应用场景：

right 常规向右移动，使得连续子数组的和满足要求
while 条件就是通过移动 left 使得从 满足要求 变成 不满足要求
这就是 单调性，只有满足了单调性才能使用双指针

209. 长度最小的子数组 ​

题目 ​

解答 ​

思路 ​

代码 ​

209. 长度最小的子数组

题目

解答

思路

代码