Minimum Size Subarray Sum

Problem

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous 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.

Solution

Two Pointers Solution: O(n) time

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int sum = 0, start = 0, res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (sum >= s) {
                res = Math.min(res, i - start + 1);
                sum -= nums[start++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res; // Do not forget to check whether we find any valid subarray  
    }
}

Analysis

The idea of this solution is that we first find a qualified subarray from the beginning
At some point after adding current number, we will have the qualified subarray
Then we use a while loop to get the smaller res
We do this by deducting sum from nums[index++] and update res with Math.min(res, i - start + 1)
We then will get the res until current index i

Notice that the time complexity is O(n) although there are two nested loops
This is because in the inner while loop, there is no index newly initialized
Each element will be visited at most twice