剑指 Offer II 008. 和大于等于 target 的最短子数组

• 剑指 Offer II 008. 和大于等于 target 的最短子数组
• • 题目
  • 题解

给定一个含有 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)) 时间复杂度的解法。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/2VG8Kg
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

连续子数组 + 子数组满足xxx条件 第一个想到的是滑动窗口的思路
先移动右边界扩大范围，扩大到子数组满足条件
再移动左边界缩小范围，缩小到子数组不满足条件
重复

right开始右移，在移动的过程中不断+nums[right]计算和，当和大于等于target的时候，更新长度最小值。
开始收缩left,在移动过程中相当于把元素踢出窗口，不断-nums[left]计算新窗口的和，当新窗口的和不满足条件时，重新开始移动right。

var minSubArrayLen = function(target, nums) {
    let sum=0;
    let len=nums.length;
    let res=len+1;//初始化为最大值,最小长度不可能是len+1
    for(let left=0,right=0;right
        sum+=nums[right];//扩展右边界
        //left<=right可以省略,因为left>right之后sum是负数，一定小于target
        while(left<=right && sum>=target){//收缩左边界，当和不满足条件或者left>right后可以停止收缩
            res = Math.min(res,right-left+1);//更新最小值
            sum-=nums[left];
            left++
        }
    }
    return res==len+1?0:res;
};

题解里看到对滑动窗口模板的总结

初始化左边界 left = 0
初始化返回值 ret = 最小值 or 最大值
for 右边界 in 可迭代对象:
	更新窗口内部信息
	while 根据题意进行调整：
		比较并更新ret(收缩场景时)
		扩张或收缩窗口大小
	比较并更新ret(扩张场景时)
返回 ret

作者：qingfengpython
链接：https://leetcode.cn/problems/2VG8Kg/solution/shua-chuan-jian-zhi-offer-day06-shu-zu-i-d5ne/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。