Leetcode:209.長度最小的子數組

給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的連續子數組。如果不存在符合條件的連續子數組，傳回 0。

示例: 

輸入:          s = 7, nums = [2,3,1,2,4,3]                
輸出: 2
解釋: 子數組          [4,3]                 是該條件下的長度最小的連續子數組。
      

進階:

如果你已經完成了O(n) 時間複雜度的解法, 請嘗試 O(n log n) 時間複雜度的解法。

解題思路：

雙指針。

1. 我們假設在pos位置往前找到的最短滿足條件的區間是[left,right],right=pos，區間的和為sum(left,pos)>=s。

2. 那麼在pos+1處，區間[left,pos+1]的總和sum(left,pos+1)>s必然成立。

3. 找最短的隻需将left右移直到sum[left,pos+1]不滿足條件即可停止移動，最終就能找到區間右邊界位于pos+1處的最短區間。

4. 重複1-3，直到數組末尾。即可傳回最小區間長度。

5. 中途遇到長度為1的區間可以停止通路。

C++代碼

class Solution { public:     int minSubArrayLen(int s, vector<int>& nums) {         int size = nums.size();         if (size <= 0) return 0;         int left = 0, right;         //确定第一個right的位置         int sum = 0, i;         for (i = 1; i <= size; i++) {             sum += nums[i - 1];             if (sum >= s) { right = i-1; break; }         }         int len_min = right - left + 1;         if (sum < s) return 0;         do{             while (sum - nums[left] >= s) {                  sum -= nums[left];                 left++;                 len_min = (right - left + 1 < len_min ? right - left + 1 : len_min);             }             right++;             if (right < size) sum += nums[right];         } while (right <= size - 1);         return len_min;     } };