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的时候，将另一个指针也向前走，并减去相应的数字，当小于的时候将元素的个数存入数组，代码如下：

1 class Solution { 2 public: 3     int minSubArrayLen(int s, vector
     
      & nums) { 4         int sz = nums.size(); 5         vector
      
        ret; 6         if(sz == 0) return 0; 7         int i = 0; 8         int j = 0; 9         int tmpSum = 0;10         while(j < sz){11             for( ; i < sz; ++i){12                 tmpSum += nums[i];13                 if(tmpSum >= s)14                     break;15             }16             if(tmpSum < s) break;　//i已经达到数组的末尾了17             for( ; j <= i; ++j){18                 tmpSum -= nums[j];19                 if(tmpSum < s)20                     break;21             }22             ret.push_back(i - j + 1);23             i++, j++;24         }25         sz = ret.size();26         if(sz == 0) return 0;27         int min = ret[0];28         for(int i = 1; i < sz; ++i){29             if(min > ret[i])30                 min = ret[i];31         }32         return min;33     }34 };
      
     

 java版本代码如下所示，对上面做了一些改进，其实完全用不到上下两个循环的，双指针一次搞定：

1 public class Solution { 2     public int minSubArrayLen(int s, int[] nums) { 3         if(nums.length == 0) 4             return 0; 5         int subSum = nums[0]; 6         int ret = Integer.MAX_VALUE; 7         int p1 = 1, p2 = 0; 8         while(p2 < p1){ 9             if(subSum < s){　　//达不到k，指针前移动或者移动到头直接返回10                 if(p1 < nums.length){11                     subSum += nums[p1];12                     p1++;13                 }else{14                     if(ret == Integer.MAX_VALUE)15                         return 0;16                     return ret;17                 }18             }else{　　　　　　//达到k，后指针向前移动并且考虑是否更新指针。19                 ret = Math.min(ret, p1-p2);20                 subSum -= nums[p2];21                 p2++;22             }23         }24         if(ret == Integer.MAX_VALUE) //如果没有找到合适的子数组的话，直接返回025             return 0;26         return ret;27     }28 }

 

新修改的方法为：

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