209. Minimum Size Subarray Sum

Question

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Algorithm

This question is a typical array question that leverage two pointers.

You get the result in your one pass. Right pointer is the main pointer who goes first then the subarray between left and right satisfies some condition, left moves.

In this case, when the sum between left and right, we can get a result and keep moving left until the sum of subarray is not large than the target.

In the end if there is no any result return 0;

A trap is that I got into is that I think the sum of subarray can only equals to the target. Then I go back to the question again to make it clear.

To be more generic, or memorable, you can regard the right pointer as the index pointer or main pointer, the left as an assistance pointer.

Code

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int left = 0, sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            while (left <= i && sum >= target) {
                res = Math.min(res, i - left + 1);
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}