Monday, August 31, 2015

Leetcode: Minimum Size Subarray Sum

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.
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
Understand the problem:
Since the array elements are all positive numbers, we could use a sliding window approach. W first move the front pointer until the sum of the subarray is greater or equal to the target value s, then we calculate the size of the window. Then we try to move the rear pointer and recalculate the window size, until the sum of the window is less than the target s. 

Code (Java):
public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (s <= 0 || nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 0;
        int hi = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        
        while (hi < nums.length) {
            // Moves the hi pointer
            while (hi < nums.length && sum < s) {
                sum += nums[hi];
                hi++;
            }
            
            // Move the lo pointer
            while (lo <= hi && sum >= s) {
                minLen = Math.min(minLen, hi - lo);
                sum -= nums[lo];
                lo++;
            }
        }
        if (minLen == Integer.MAX_VALUE) {
            return 0;
        } else {
            return minLen;
        }
    }
}

No comments:

Post a Comment