209. Minimum Size Subarray Sum

1. Description

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

2. Example

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

3. Constraints

• 1 <= target <= $10^9$
• 1 <= nums.length <= $10^5$
• 1 <= nums[i] <= $10^5$

4. Follow Up

• If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

5. Solutions

Sliding Window

n = nums.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    int minSubArrayLen(int target, const vector<int> &nums) {
        int min_length = INT_MAX;
        for (int slow = 0, fast = 0, sum = 0; fast < nums.size(); ++fast) {
            sum += nums[fast];

            while (sum >= target) {
                min_length = min(fast - slow + 1, min_length);

                sum -= nums[slow];
                ++slow;
            }
        }

        return min_length == INT_MAX ? 0 : min_length;
    }
};