Minimum-Size-Subarray-Sum.md

##Minimum Size Subarray Sum

23% Accepted

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 -1 instead.

Have you met this question in a real interview? Yes
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.

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

####Tags Expand

• Two Pointers Array

####暴力解法 O(n2)

public class Solution {
    /**
     * @param nums: an array of integers
     * @param s: an integer
     * @return: an integer representing the minimum size of subarray
     */
    public int minimumSize(int[] nums, int s) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int size = nums.length;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < size; i++) {
            int sum = 0;
            int length = 0;
            for (int j = i; j < size; j++) {
                sum = sum + nums[j];
                length++;
                if (sum >= s) {
                    min = Math.min(min, length);
                }
            }
        }
        if (min != Integer.MAX_VALUE){
            return min;
        } else {
            return -1;
        }
    }
}

####O(nlogn)解法 O(nlgn)的解法，这个解法要用到二分查找法， 思路是，我们建立一个比原数组长一位的sums数组，其中sums[i]表示nums数组中[0, i - 1]的和， 然后我们对于sums中每一个值sums[i]，用二分查找法找到子数组的右边界位置，使该子数组之和大于sums[i] + s，然后我们更新最短长度的距离即可。代码如下：

####优化解法 O(n)

• 前提条件是 没有负数
• 前向型two pointers
• 先想清楚规律,自己画图找i j范围
• 已经[0,4] 已经找到满足条件,就不需要找[0,5] [0,6] 了
• 然后i++ sum 减去nums[i] 变成[1,4]去找是否满足,如果满足,就不用找[1,5],而是i++去找[2,4]
• 如果不满足 就去找[1,5]

public class Solution {
    /**
     * @param nums: an array of integers
     * @param s: an integer
     * @return: an integer representing the minimum size of subarray
     */
    public int minimumSize(int[] nums, int s) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int size = nums.length;

        for (int i = 0; i < size; i++) {
            if (nums[i] >= s) {
                return 1;
            }
        }

        int sum = 0;
        int i = 0;
        int j = 0;
        int count = 0;
        int min = Integer.MAX_VALUE;

        for (i = 0; i < size; i++) {

            while (sum < s && j < size) {
                sum += nums[j++];
                count++;
            }
            if (sum >= s) {
                min = Math.min(min, count);
            }
            sum -= nums[i];
            count--;

        }
        return (min == Integer.MAX_VALUE) ? -1 : min;
    }
}