Wednesday, July 22, 2015

Minimum Size Subarray Sum -- Leetcode

Question:
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.
Answer:
traverse the array one time, Optimal method, using O(n)!

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int start=0,end=0;
        int n=nums.length;
        if(n==0){
            return 0;
        }
        int currsum=nums[0];
        int minLen=n+1;
        boolean flag = false;
       
        while(start<=end && end<n){
            //if not satisfy the constraint, keep end index ++ and adding shift elements until satisfy.
            while(currsum < s){
                if(end<n-1){
                    currsum += nums[++end];
                }else{// end index arrived to n-1.
                    if(flag == true){     //have found one.
                        return minLen;
                    }else{
                        return 0;
                    }
                }
            }
            //if satisfy the constraint, keep start index ++ and substracting shift elements until not satisfy again.
            while(currsum >= s){
                int len = end-start+1;

                if(len < minLen){
                    minLen = len;
                    flag = true;
                }
                if(start<=end){
                   currsum -= nums[start++];
                }
            }
        }
        return minLen;
    }
}

No comments:

Post a Comment