輸入一個數組和一個數s,求數組中的子數組的連續和>=s中最短的子數組

第一次的做法是：

先處理前綴和，然后二重循環枚舉子數組，用前綴和sum[j]-sum[i-1]取得子數組的連續和，與s比較，更新答案。ON^2，超時

第二次做法：

既然ON^2超時，說明肯定是NlgN或者ON的做法，這題數組無序而且也不能排序之后做，所以也不可能是NlgN的做法，那么只有ON的做法，于是想到指針法

用兩個指針i,j，初始都指向數組的第一個元素，然后遍歷數組，求和：

1.sum>=s，更新答案，并且i++，注意i==j的情況要i++,j++

2.sum<s，說明現在和還不夠，所以j++

1 class Solution { 2 public: 3 int minSubArrayLen(int s, vector<int>& nums) { 4 int len=nums.size(); 5 if(len==0) return 0; 6 int i=0,j=0; 7 int sum=nums[0]; 8 int ans=INT_MAX; 9 while(j<len){ 10 if(sum<s){ 11 sum+=nums[++j]; 12 } 13 else if(sum>=s){ 14 sum-=nums[i]; 15 ans=min(ans,j-i+1); 16 if(i==j){ 17 i++; 18 j++; 19 } 20 else i++; 21 } 22 } 23 if(ans!=INT_MAX) return ans; 24 return 0; 25 } 26 };

?

轉載于:https://www.cnblogs.com/0summer/p/5829694.html

總結

以上是生活随笔為你收集整理的leetcode-Minimum Size Subarray Sum-209的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。