209. 长度最小的子数组

[blueWind123731]

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

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

进阶：

如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

https://leetcode-cn.com/problems/minimum-size-subarray-sum/

[blueWind123731]

双指针

时间复杂度：O(n) 空间复杂度：O(1)

var minSubArrayLen = function(s, nums) {
    if(nums.length===0){
        return 0
    }
    let sum = 0
    let l=0,r=0;
    let ans = Infinity
    let n = nums.length
    while(r<n){
        sum += nums[r]
        while(sum>=s){
            ans = Math.min(ans,r-l+1)
            sum -= nums[l]
            l++
        }
        r++
    }
    return ans===Infinity?0:ans
};

[blueWind123731]

暴力法

时间复杂度：O(n²) 空间复杂度：O(1)

var minSubArrayLen = function(s, nums) {
    let n = nums.length
    if(n===0){
        return 0
    }
    let ans = Infinity
    for(let i=0;i<n;i++){
        let sum = 0
        for(let j=i;j<n;j++){
            sum += nums[j]
            if(sum>=s){
                ans = Math.min(ans,j-i+1)
                break
            }
        }
    }
    return ans===Infinity?0:ans
};