209.长度最小的子数组

【LetMeFly】209.长度最小的子数组

力扣题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

给定一个含有 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 <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

 

进阶：

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

方法一：滑动窗口

使用两个指针$l$和$r$，其中$l$指向“符合答案的子数组的第一个元素的前一个元素”，$r$指向“符合答案的子数组的最后一个元素”

初始时，没有任何一个元素处于“滑动窗口”中，因此$l$为$-1$，然后$r$从下标$0$开始遍历数组。

每次$r$遍历到一个新的元素，就把这个元素加到“窗口总和”中。

当左指针和右指针之间有间距时，不断尝试去掉左指针的下一个元素，如果去掉后窗口中元素总和小于$target$了，就取消这次“移除尝试”

这样，$r$每次遍历一个数组中的元素，就能得到以$r$结尾的满足$和\geq target$的最小窗口（或前$r$个元素的和仍不足$target$）

如果窗口中的元素的和不小于$target$，就更新答案最小值。

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

AC代码

C++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = INT_MAX;
        int l = -1;  // (l, r]
        int s = 0;
        for (int r = 0; r < nums.size(); r++) {
            s += nums[r];
            while (l + 1 < r && s - nums[l + 1] >= target) {
                s -= nums[l + 1];
                l++;
            }
            if (s >= target) {
                ans = min(ans, r - l);
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126461543