209. Minimum Size Subarray Sum

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.

click to show more practice.

More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

思路: 双指针来做, 找到window的sum >= s的最小的window长度。用Left跟Right两个指针分别表示window的左边界跟右边界。新来一个数,如果sum>=s,则记录当前最小的窗口长度minLen=min(minLen,right-left), 并将left左边界右移;如果sum<s, 则需要扩大window边界,将右边界右移。 注意循环的条件: right<=left && right <nums.length; 注意最后比较minLen跟num.length, 注意退出条件,当right移到最右侧的时候,还要移动左边界往右移,缩小window长度
,来看是否有更优解法.
复杂度: Time O(n), Space: O(1)

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int left = 0, right = 0, minLen = Integer.MAX_VALUE, sum = 0;
        while(left <= right && right < nums.length) {
            if (sum < s) { // sum of window less than s
                if (right < nums.length) {
                    sum = sum + nums[right];
                }
                right++;
            } else { // sum of window greater equal than s
                int windowLen = right - left;
                minLen = Math.min(minLen, windowLen);
                sum = sum - nums[left];
                left++;
            }
        }
        return minLen < nums.length ? minLen : 0;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s