LeetCode 209： Minimum Size Subarray Sum（長度最小的子數(shù)組）

Q:Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

翻譯君：
給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的連續(xù)子數(shù)組。如果不存在符合條件的連續(xù)子數(shù)組，返回 0媳否。

看到這個題目定躏，需要和面試官交流的問題:

1.什么是子數(shù)組梅桩。因為子數(shù)組的在不同的題目定義是不一樣的麻车，有的不一定要求是連續(xù)的元素。

2.關于一些特殊解准浴。比如沒有解返回什么，這里題目已明確說明了如果沒有滿足sum>=s的就返回0

如果有多個解是返回哪一組捎稚？這里因為返回的是長度乐横，所以只會有一個答案。如果返回的是一個子數(shù)組阳藻，就需要考慮這個問題晰奖。

當然，第一時間想到的肯定就是暴力解法了腥泥，差一點的時間復雜度O(n^{3)匾南，優(yōu)化一下最好可以達到O(n}2)』淄猓肯定都不是我們滿足的了蛆楞。

那么有什么比較厲害的解法呢？

這里要說一個詞叫做“滑動窗口”夹厌，和之前說的“指針碰撞”有一點像豹爹。只不過這是兩個指針組成的一塊像窗口一樣的區(qū)域。只需要通過不斷移動這個窗口就可以解決這個問題了矛纹。

下圖的紅色區(qū)域就是上面所說的窗口臂聋。

minsubarray.png

關鍵在于怎么移動這個窗口解決此題呢

（1）首先區(qū)間[i,j]的定義很重要
要保證最開始的時候窗口不包含元素，很簡單，只需要將j=-1就好了

 int i=0; int j=-1;

（2）初始化的長度為數(shù)組的長度+1孩等。因為要保證在有符合條件的子數(shù)組情況下艾君，這個值初始值最好是最大值也就是數(shù)組的長度加1

（3）最后就是移動窗口了。
首先要保證窗口不越界肄方，

然后如果子數(shù)組小于目標和冰垄，右指針j右移，使窗口變大

如果子數(shù)組大于目標和权她，左指針j右移虹茶，使窗口變小

之后判斷如果子數(shù)組元素和大于目標和并且此時符合子數(shù)組的長度變小了，則取這個較小的子長度

（4）需要注意的是數(shù)組如果為空隅要，或者沒有找到符合條件的子數(shù)組蝴罪，那么就返回0。也即我的子數(shù)組長度len和初始值一樣沒有改變拾徙，返回0.

此處需要上一波完整代碼了

int minSubArrayLen(int s, vector<int>& nums) {
        int i=0; int j=-1; //保證開始的時候窗口不包含元素
        int sum=0;
        int len=nums.size()+1;  //初始化的長度為數(shù)組的長度洲炊，假設存在子數(shù)組元素和大于目標和，那么這個值肯定是最大值

        while(i<nums.size()){
          
            if(sum<s&&j+1<nums.size()) sum+=nums[++j];   //如果子數(shù)組小于目標和尼啡，右指針右移暂衡，使窗口變大
            else sum-=nums[i++];                         //如果子數(shù)組大于目標和，左指針右移崖瞭，使窗口變小

            if(sum>=s&&len>j-i+1) len=j-i+1;              //如果子數(shù)組元素和大于目標和并且此時符合子數(shù)組的長度變小了狂巢，則取這個較小的子長度
        }
        if(len==nums.size()+1)  return 0;
        return len;
    }

測試一下效率，結(jié)果還是很帥的书聚，看下圖【滑稽笑】：

image.png