Minimum Size Subarray Sum 406

Question

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.

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).

Solution

遍历数组，到i时，找到以i元素开头的最短的子数组，若比最短子数组小则更新。

O(nlogn)的算法之后补上。

代码如下：

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 min = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++){
            int count = i;
            int sum = nums[count];
            while(sum < s){
                count++;
                if(count >= nums.length){
                    break;
                }
                sum += nums[count];
            }

            if(count >= nums.length){
                break;
            }

            min = Math.min(min, count - i + 1);
        }

        if(min == Integer.MAX_VALUE){
            return -1;
        }

        return min;
    }
}