209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous 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.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Solution: 

Two pointers.

Use two pointers i and j to traverse the array, when sum[i->j] >=s, increment i to find the maximum i that still can make sum[i->j] >=s update result accordingly.

It use some sort of greedy here, because all elements are positive number so if sum[i->j]>=s then sum[i -> j+1] must >=s as well. Each iteration of j will give us the minimum subarray that ends at j with sum>=s. For finding minimum subarray that end with j+1, only increasing i will possibly give us a better result. So the entire solution will have at most about 2n of time complexity because i and j will always increase till n. 

Time complexity O(n)

  public int minSubArrayLen(int s, int[] nums) {  
    int i=0;  
    int j=0;  
    int res=nums.length+1;  
    int sum=0;  
    while(j<nums.length){  
      sum+=nums[j++];  
      if(sum>=s){  
        while(sum>=s){  
        sum-=nums[i++];  
       }  
      res=Math.min(res,j-i+1);  
      }   
    }  
    return res==nums.length+1 ? 0: res;  
   }