Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn‘t one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
题意就是要找出数组中的最短子数组，其和不小于给定值s。刚开始的想法很简单，两层循环，但耗时过多300ms。改进后，只需遍历一次，维护两个标志low和high，让low和high之间的子数组不小于给定值s，然后求最短，耗时4ms。另外，感觉测试数据不够全面，将求和值sum换为int型，也可以通过（本人以为只是测试数据未考虑全面，若s=2^32-1，数组array[2^32-2，2]，sum就会越界，所以建议sum定义为long long 型）。
代码1：
1 int minSubArrayLen(int s, vector<int>& nums) 2 { 3 int size=nums.size(); 4 if (size==0) 5 return 0; 6 int minLen=size+1; 7 for (int i=0;i<size;i++) 8 { 9 int n=0; 10 long long sum=0; 11 for (int j=i;j<size;j++) 12 { 13 sum=sum+nums[j]; 14 ++n; 15 if (sum>=s) 16 { 17 if(minLen>n) 18 minLen=n; 19 break; 20 } 21 } 22 } 23 if(minLen==size+1) 24 return 0; 25 return minLen; 26 }
改进后代码：
1 int minSubArrayLen(int s, vector<int>& nums) 2 { 3 int size=nums.size(); 4 int minLen=size+1,low=0,high=0; 5 long long sum=0; 6 while(high<size) 7 { 8 sum+=nums[high]; 9 ++high; 10 while(sum>=s) 11 { 12 minLen=min(minLen,high-low); 13 sum-=nums[low]; 14 ++low; 15 } 16 } 17 if(minLen==size+1) 18 return 0; 19 return minLen; 20 }
209. Minimum Size Subarray Sum
原文：http://www.cnblogs.com/zhang-hill/p/5132798.html