Minimum Size Subarray Sum 最短子数组之和(Medium)

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.

解法1：Slide Window(Two Pointers)

时间复杂度：O(n)，空间复杂度：O(1)

public int minSubArray(int[] arrs, int target) {
    if (null == arrs || arrs.length == 0) {
        return 0;
    }

    int left = 0;
    int right = 0;
    int min = arrs.length+1;
    int sum = 0;

    while(right < arrs.length) {
        sum += arrs[right];

        while(sum >= target) {
            sum -= arrs[left];
            min = Math.min(min,right-left+1);
            left++;
        }
        right++;
    }

    return min==(arrs.length+1) ? 0 : min;
}

解法2：Binary Search

时间复杂度：O(nlogn)，空间复杂度：O(n)

//在arrs数组中查找<=target的最大值的索引
public int binarySearch(int[] arrs,int target,int start,int end) {
    while(start+1 < end) {
        int mid = start +(end-start)/2;
        if(arrs[mid] >= target) {
            end = mid;
        } else {
            start = mid;
        }
    }

    if(arrs[end] <= target) {
        return end;
    } else {
        return start;
    }
}

public int minSubArray2(int[] arrs, int target) {
    if (null == arrs || arrs.length == 0) {
        return 0;
    }

    int len = arrs.length;
    int min = arrs.length+1;

    int[] sums = new int[len+1];

    for(int i=0; i<len;i++) {
        sums[i+1] = sums[i] + arrs[i];
        if (sums[i + 1] >= target) {
            int left = binarySearch(sums, sums[i + 1] - target, 0, i + 1);
            min = Math.min(min, i + 1 - left);
        }
    }

    return min==(arrs.length+1) ? 0 : min;
}

References:

• LeetCode Minimum Size Subarray Sum