209. 长度最小的子数组

209. 长度最小的子数组

难度中等487

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

示例：

<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgba(var(--grey-9-rgb),0.04); padding: 10px 15px; color: rgba(var(--grey-9-rgb),1); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。</pre>

思路一（暴力破解法）时间复杂度

int minSubArrayLen(int s, int* nums, int numsSize){
    int min = 1000000;
    for(int i = 0; i < numsSize;i++){
        int sum = 0;
        for(int j = i;j<numsSize;j++){
            sum += nums[j];
            if(sum >= s){
                int len = j - i + 1;
                if(len < min){
                    min = len;
                }
                break;
            }
        }
    }

    if(min == 1000000) return 0;
    return min;
}

思路二（滑动窗口）时间复杂度O(n)

int minSubArrayLen(int s, int* nums, int numsSize){
    int start = 0,end = 0;
    int min = 1000000;
    int len = 0;
    int duration = 0;
    while(end < numsSize){
        while(duration < s && end < numsSize){//滑动窗口的右端右移，相当于注入新的元素。
            duration += nums[end++];
        }
        while(duration >= s && start < end){//start用于标记滑动窗口中最左的元素
            len = end -start;
            if(len < min) min = len;//首先把满足条件的滑动窗口的最小值记录下来
            duration -= nums[start++];   //然后让滑动窗口的左端右移
        }
    }
    if(min == 1000000) return 0;
    return min;
}

image.png