Two-pointer Java O(n) solution


  • 0
    F

    Basically we use two indices i and j to maintain a subarray from nums[i] to nums[j] and a variable sum to store the sum of elements in this subarray. Whenever sum is less than the given value s, we keep extending the subarray to the right. When sum is no less than s, a candidate subarray is found so we can update the minimum length. Note now sum >= s, which means it's more than needed, so we can start dumping elements from the beginning to shorten the subarray until sum < s. Then again we need to extend the subarray to the right and repeat. A nice fact here about the minimum length is that it cannot be larger than the length of the given array. So if we initialize the minimum length with some value greater than the length of the given array and at the end the minimum length is still greater than this length, then we know no candidate subarray has been found so zero is returned. Here is the program:

    public int minSubArrayLen(int s, int[] nums) {
        int minLen = nums.length + 1;  // minimum length of the subarray, initialized with some value greater than nums.length
        int i = 0;                     // beginning index of the subarray
        int j = 0;                     // ending index of the subarray
        int sum = nums.length > 0 ? nums[0] : 0;  // sum of the subarray, sum = nums[i] + nums[i + 1] + ... + nums[j]
    	
        while (j < nums.length && i <= j) {
    	if (sum < s && ++j < nums.length) { 
    	    sum += nums[j];	   // sum comes short so just keep adding
    	} else {  
    	    minLen = minLen < j - i + 1 ? minLen : j - i + 1;  // sum is no less than the given value s, so update the minimum length
    	    sum -= nums[i++];  // since sum now is more than needed, we start removing elements from the beginning of the subarray
    	}
        }
    	
        return minLen > nums.length ? 0 : minLen;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.