Minimum Size Subarray Sum

gistfile1.java

// O(n)
public class Solution {
    /*
        [2,3,1,2,4,3] and s = 7
          4 3
    */
    public int minSubArrayLen(int s, int[] nums) {
        if (s < 0 || nums == null || nums.length == 0)
            return 0;
        int start = 0, end = 0, sum = 0, res = 0;
        while (end < nums.length && sum < s) {
            sum += nums[end];
            res++;
            if (sum >= s)
                break;
            end++;
        }
        if (end == nums.length)
            return 0;
        while (end < nums.length && start <= end) {
            if (sum - nums[start] >= s) {
                sum -= nums[start];
                start++;
                res = Math.min(res, end - start + 1);
            } else {
                end++;
                if (end >= nums.length) break;
                sum += nums[end];
            }
        }
        return res;
    }
}

// O(nlogn)
public class Solution {
    /*
        [2,3,1,2,4,3] and s = 7
          4 3
    */
    public int minSubArrayLen(int s, int[] nums) {
        if (s < 0 || nums == null || nums.length == 0)
            return 0;
        int[] sums = new int[nums.length + 1];
        for (int i = 1; i < sums.length; i++) {
            sums[i] = nums[i - 1] + sums[i-1]; //err
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < sums.length; i++) {
            int end = Arrays.binarySearch(sums, i, sums.length, sums[i] + s);
            if (end >=0) {
                res = Math.min(res, end - i);
            } else {
                int insertion = -(end + 1);
                if (insertion != sums.length)
                    res = Math.min(res, insertion - i);
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}