Minimum Size Subarray Sum - Lintcode

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.

Analysis

A straightforward solution contains two loops which have complexisty of O(n²). A better solution should only have complexity of O(n).

Straightforward solution O(n²)

public int minimumSize(int[] nums, int s) {
    if (nums.length == 0){
        return -1;
    }

    int length = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++){
        int sum = 0;
        for (int j = i; j < nums.length; j++){
            sum += nums[j];

            if (sum >= s){
                length = Math.min(length, j - i + 1);
                break;
            }
        }
    }

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

A better solution O(n)

 public int minimumSize(int[] nums, int s) {
    if (nums.length == 0) {
        return -1;
    }

    int length  = Integer.MAX_VALUE;
    int j = 0;
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        while (j < nums.length && sum < s) {
            sum += nums[j];
            j++;
        }

        if (sum >= s) {
            length = Math.min(length, j - i);
        }

        sum -= nums[i];
    }

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