209 Minimum Size Subarray Sum

209. Minimum Size Subarray Sum

1. Question

Given an array ofnpositive integers and a positive integers, find the minimal length of acontiguoussubarray of which the sum ≥s. If there isn't one, return 0 instead.

For example, given the array[2,3,1,2,4,3]ands = 7, the subarray[4,3]has the minimal length under the problem constraint.

2. Implementation

(1) Two Pointers

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int sum = 0, minLen = Integer.MAX_VALUE;

        for (int start = 0, end = 0; end < nums.length; end++) {
            sum += nums[end];

            while (sum >= s) {
                minLen = Math.min(minLen, end - start + 1);
                sum -= nums[start];
                ++start;
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

(2) Binary Search

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }

        int minLen = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int index = binarySearch(prefixSum, i + 1, n, prefixSum[i] + s);

            if (index != -1) {
                minLen = Math.min(minLen, index - i);
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    public int binarySearch(int[] prefixSum, int start, int end, int target) {
        int mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;

            if (prefixSum[mid] < target) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }

        if (prefixSum[start] >= target) {
            return start;
        }
        else if (prefixSum[end] >= target) {
            return end;
        }
        else {
            return -1;
        }
    }
}

3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(1)

Binary Search: 时间复杂度O(nlogn), 空间复杂度O(1)