Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/description/

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.

Thoughts

因为原数组又没排好序，而要找的是 连续 的最短子数组（窗口），因此不能先排序也就不能对index作二分。 题目要的是长度，自然想到可以对子数组可能的长度做二分。 二分的前半段是长度不足以使得任何窗口的值大于等于s, 后半段是长度足矣。 如何判断长度是否足够呢？对数组做下遍历，保留一个size为len的窗口，计算窗口向前移时窗口总和。

Code

class Solution {
    private int calcLenSubArr(int len, int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < len; i++) {
                sum += nums[i];
        }

        for (int i = len; i < nums.length; i++) {
            if (sum >= s) {                   
                break;
            }
            sum -= nums[i - len];
            sum += nums[i];
        }

        return sum;
    }


    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int start = 1, end = nums.length;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int sum = calcLenSubArr(mid, nums, s);
            if (sum == s) {
                end = mid;
            } else if (sum < s) {
                start = mid;
            } else {
                end = mid;
            }
        }

        int tmp = calcLenSubArr(start, nums, s);
        if (tmp >= s) {
            return start;
        } else {
            tmp = calcLenSubArr(end, nums, s);
            if (tmp >= s) {
                return end;
            } else {
                return 0;
            }
        }       
    }
}

Analysis

一共lgn次循环，每次循环O(n)遍历，总时间O(nlgn)