题目

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

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：

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

解题思路：

双指针：

一个左指针，一个右指针。

右指针不断右移，直到 s >= target 时开始判断

先记录一下长度，然后不断右移 left。

最后判断一下 ans，因为有可能 nums 中所有的和不足 target

代码：

Python

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        from math import inf
        ans = inf
        left = 0
        s = 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 != inf else 0

C++

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = nums.size() + 1;
        int s = 0;
        int left = 0;
        for(int right = 0; right < nums.size(); right++) {
            s += nums[right];
            while (s - nums[left] >= target) {
                s -= nums[left];
                left += 1;
            }
            if (s >= target) {
                ans = min(ans, right - left + 1);
            }
        }
        return ans == nums.size() + 1 ? 0 : ans;
    }
};

时间复杂度：O(N)

空间复杂度：O(1)