題目：長度最小的子數(shù)組

描述：
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。

找出該數(shù)組中滿足其總和大于等于 target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0 。

示例 1：

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。

leetcode鏈接

方法一：滑動(dòng)窗口
滑動(dòng)窗口有兩種：一種是固定大小的窗口，另一種是動(dòng)態(tài)大小的窗口，而本題要求長度最小的子數(shù)組，所以應(yīng)該用動(dòng)態(tài)大小的窗口，滑動(dòng)窗口基于雙指針的思想：
我們定義兩個(gè)指針left和right表示窗口的兩端，定義一個(gè)minLen變量表示最端短的長度，初始時(shí)指針都指向0，此時(shí)如果窗口內(nèi)的數(shù)之和小于目標(biāo)數(shù)target，那么right指針右移，窗口變大，相反如果窗口內(nèi)的數(shù)之和大于目標(biāo)數(shù)target，那么更新minLen,并且移動(dòng)left指針，直到窗口內(nèi)的數(shù)之和小于目標(biāo)數(shù)target為止。最后遍歷完數(shù)組，minLen即為長度最小的子數(shù)組
時(shí)間復(fù)雜度；o(n)
空間復(fù)雜度：o(1)

int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int minLen = n+1;int left = 0,right = 0;int sum = 0;while(right<n){sum+=nums[right];while(sum>=target){minLen = min(minLen,right-left+1);sum-=nums[left];left++;}right++;}//如果minLen沒有更新過，即為不存在滿足條件的子數(shù)組，返回0return minLen==n+1?0:minLen;}

方法二：暴力法
我們枚舉數(shù)組中的每一個(gè)元素為子數(shù)組的起始元素，然后找到從枚舉的元素開始滿足條件的最小子數(shù)組的長度，再維護(hù)最小的子數(shù)組長度，即可找到答案。
時(shí)間復(fù)雜度：o(n2)
空間復(fù)雜度：o(1)

int minSubArrayLen(int s, vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;for (int i = 0; i < n; i++) {int sum = 0;for (int j = i; j < n; j++) {sum += nums[j];if (sum >= s) {ans = min(ans, j - i + 1);break;}}}return ans == INT_MAX ? 0 : ans;}

方法三：前綴和+二分查找
暴力法中枚舉子數(shù)組起始元素的時(shí)間復(fù)雜度為o(n),找到最小子數(shù)組的時(shí)間復(fù)雜度為o(n),此時(shí)我們考慮優(yōu)化尋找最小子數(shù)組的時(shí)間，注意到我們給定的數(shù)組的所有的元素都是大于0的，那么我們每一個(gè)元素的前綴和都是遞增的，因此我們可以利用二分查找來查找最小子數(shù)組，如果我們枚舉第i個(gè)元素為最小子數(shù)組的起始元素，那么我們二分查找的元素可以變?yōu)閠arget+i的前綴和，而此時(shí)找到的目標(biāo)元素的前綴和-i的前綴和 = target，因此我們找到的元素即為最短子數(shù)組的末尾，然后我們?cè)倬S護(hù)最短的一個(gè)長度
時(shí)間復(fù)雜度：o(nlogn) 二分查找的時(shí)間復(fù)雜度為logn
空間復(fù)雜度：o(n) 存儲(chǔ)前綴和的空間為o(n)
注意：注意二分查找時(shí)的left和right指針的取值

int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int minLen = n+1,mid = 0;vector<int> sum(n+1,0);//sum[i]表示前i個(gè)數(shù)之和 for(int i=1;i<=n;i++){sum[i] = sum[i-1]+nums[i-1];}for(int i=1;i<=n;i++){//枚舉每個(gè)元素為子數(shù)組的起始元素//注意i為第i個(gè)元素，而第i個(gè)元素的下標(biāo)為i-1int tag = target+sum[i-1];//這里的left和right表示的為第幾個(gè)元素，由于sum[i]為第i個(gè)元素的前綴和int left = i,right = n;while(left<right){mid = (left+right)/2;if(tag>sum[mid]){left = mid+1;}else{//我們要找的數(shù)為大于等于tag，所以right=mid，而不是mid-1right = mid;}}if(sum[left]>=tag){minLen = min(left-i+1,minLen);}}return minLen==n+1?0:minLen;
}