209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous 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.

Note: 如果输入数组含有negative，Solution2不行，Solution1也不行？
做法？: 相同，对负数单独判断一下是否累计和为负数，如果是的话，drop所有原来的？

Solution1：滑动窗(two pointers)

思路： 滑动窗[start, i] i keeps moving forward, 并纪录滑动窗内sum，保证窗内的sum一定是小于s的，当sum>=s时，窗的左start 跟上，并从sum中吐出元素。在此过程中纪录滑动窗的最小length。
Time Complexity: O(N) Space Complexity: O(1)

Solution2：Integral sum + Binary Search

思路： 建立累积和数组(积分) sums[]，现在要找到sum[end] - sum[start] >=s 并 end-start最小。因为输入数组都是positive，所以sums[]是递增序列，对每一个sums[i]，去binary search “sums[i] + s”，返回该位置index。在binary search中，尽可能找到距离i最近的index，也就是尽可能靠左，if(sums[mid] == target) hi = mid - 1; 找不到的情况：if(index == sums.length) break。此过程中纪录更新最小的min_len = end - i;

Time Complexity: O(N logN) Space Complexity: O(N)

Solution1 Code：

class Solution1 {
    public int minSubArrayLen(int s, int[] nums) {
        int sum = 0;
        int min_len = Integer.MAX_VALUE;
        int start = 0;
        
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while(sum >= s) {
                min_len = Math.min(min_len, i - start + 1);
                sum -= nums[start++];
            }
        }
        return min_len == Integer.MAX_VALUE ? 0 : min_len;
    }
}

Solution2 Code：

class Solution2 {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        
        // integral: accumulate sum
        int sums[] = new int[nums.length + 1];
        for(int i = 1; i < sums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        
        // binar search, for every sums[i],
        // find the sum[end] that sum[end] - sum[i] == s, or > s but nearest, 
        // and update min_len = end - i.
        int min_len = Integer.MAX_VALUE;
        for(int i = 0; i < sums.length; i++) {
            
            int index = binarySearch(sums, i + 1, sums.length - 1, sums[i] + s);
            
            // not found case:
            // like when s = 4, sums[i] = 3, sums[j] needs 7, or larger than 7 but nearest
            // sums = [1, 2, 3, 4, 5] will return index=5, 
            if(index == sums.length) break;
            
            if(index - i < min_len) min_len = index - i;
        }
        
        return min_len == Integer.MAX_VALUE ? 0 : min_len;    
    }
    
    private int binarySearch(int[] sums, int lo, int hi, int target) {
        // find the qualified smallest one
        while(lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if(sums[mid] == target) {
                hi = mid - 1;
            }
            else if(sums[mid] > target) {
                hi = mid - 1;
            }
            else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

最后编辑于：2017.11.29 07:30:45