题目描述

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

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [nums_l, nums_l+1, ..., nums_r-1, nums_r]，并返回其长度。如果不存在符合条件的子数组，返回 0。

样例

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

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

输入：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)$ 时间复杂度的解法。

算法

(双指针) $O(n)$

1. 对于每个位置 $i$，找到尽可能大的位置 $j$，满足 $[j, i]$ 的和严格小于 $target$。由于 $j$ 是随着 $i$ 增大而单调不减的，故我们可以用双指针实现这个过程，并在移动 $j$ 的过程中，不断更新最短长度。

时间复杂度

• 每个数最多访问两次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

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

        int ans = INT_MAX, cur = 0;
        for (int i = 0, j = 0; i < n; i++) {
            cur += nums[i];

            while (j <= i && cur >= target) {
                if (ans > i - j + 1)
                    ans = i - j + 1;

                cur -= nums[j];
                ++j;
            }
        }

        if (ans == INT_MAX)
            return 0;

        return ans;
    }
};