209. 長度最小的子數(shù)組

難度中等487

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s 壮不，找出該數(shù)組中滿足其和 ≥ s 的長度最小的 連續(xù) 子數(shù)組，并返回其長度贡避。如果不存在符合條件的子數(shù)組砂缩，返回 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
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。</pre>

思路一（暴力破解法）時(shí)間復(fù)雜度

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;
}

思路二（滑動(dòng)窗口）時(shí)間復(fù)雜度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){//滑動(dòng)窗口的右端右移，相當(dāng)于注入新的元素香璃。
            duration += nums[end++];
        }
        while(duration >= s && start < end){//start用于標(biāo)記滑動(dòng)窗口中最左的元素
            len = end -start;
            if(len < min) min = len;//首先把滿足條件的滑動(dòng)窗口的最小值記錄下來
            duration -= nums[start++];   //然后讓滑動(dòng)窗口的左端右移
        }
    }
    if(min == 1000000) return 0;
    return min;
}

image.png