209. Minimum Size Subarray Sum

1.brute-force, O(n^3)

public int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i; j < nums.length; j++) {
            if (sum(nums, i, j) >= s)
                res = Math.min(res, j - i + 1);
        }
    }
    return res == Integer.MAX_VALUE ? 0 : res;
}

private int sum(int[] nums, int i, int j) {
    int sum = 0;
    for (int k = i; k <= j; k++) {
        sum += nums[k];
    }
    return sum;
}

2.two-pointers O(n^2)

public int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int i = 0;
    int j = 0;

    int res = Integer.MAX_VALUE;

    while (i < nums.length && j < nums.length) {
        if (sum(nums, i, j) < s) {
            j++; 
        } else {
            res = Math.min(res, j - i + 1);
            i++;
        }
    }
    return (res == Integer.MAX_VALUE) ? 0 : res;
}

private int sum(int[] nums, int i, int j) {
    int sum = 0;
    for (int k = i; k <= j; k++) {
        sum += nums[k];
    }
    return sum;
}

3.two-pointers, O(n)

public int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int i = 0;
    int j = -1;

    int sum = 0;
    int res = nums.length + 1;

    while (i < nums.length) {
        if (j + 1 < nums.length && sum < s) {
            sum += nums[++j];
        } else {
            sum -= nums[i++];
        }

        if (sum >= s) res = Math.min(res, j - i + 1);
    }
    return (res == nums.length + 1) ? 0 : res;
}