209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integers, find the minimal length of acontiguoussubarray of which the sum ≥s. If there isn't one, return 0 instead.

For example, given the array[2,3,1,2,4,3]ands = 7,
the subarray[4,3]has the minimal length under the problem constraint.

click to show more practice.

More practice:

If you have figured out theO(n) solution, try coding another solution of which the time complexity isO(nlogn).

Solution)

We can use a dynamic sliding window for the array to find the minimum size subarray sum.

First we can start from the first element. Then, we can enlarge the window size by moving the end.

If the current sum is less than the given s, we can continue to enlarge. But, the end point is should be inside the array.

If the current sum is greater than or equal to s, we have to update the minimum length by comparing the current minimum length and the current subarray length.

Then, we have to shrink the window by moving the start index.

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int start=0, end=0, minLen=0;
        int currentSum = 0;
        while (start<nums.length) {
            if (currentSum < s && end < nums.length)
                currentSum += nums[end++];
            else if (currentSum >= s) {
                if (minLen == 0 || end-start < minLen)
                    minLen = end-start;
                currentSum -= nums[start];
                start++;
            } else break;
        }
        return minLen;
    }
}