209. Minimum Size Subarray Sum Medium

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

Approach

Input: An array of positive integers nums and a positive integer target.

Output: Find the minimal length of a contiguous subarray whose sum is greater than or equal to target. Return 0 if it doesn't exist.

This problem falls under the Variable-length Sliding Window category.

We use two pointers (left and right) to maintain a sliding window, and use a variable to keep track of the sum of elements within the window. Every time the right pointer moves to the right, add the current element to the window sum; when the sum becomes greater than or equal to target, it implies the current window represents a valid solution. At this point, try to continuously move the left pointer to shrink the window in order to find an even shorter valid subarray, and update the minimal length.

During the entire process, dynamically adjust the window size, and update the minimum value whenever the condition is met. Finally, return the recorded minimal length. If no window satisfied the conditions, return 0.

Implementation

python

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0                      # Left boundary of the sliding window
        n = len(nums)
        min_len = float('inf')       # Initialize min length as infinity
        window_sum = 0               # Sum of elements in current window

        for right in range(n):
            window_sum += nums[right]  # Expand window, add right end element

            # When sum of elements in window >= target, start shrinking left boundary
            while window_sum >= target:
                min_len = min(min_len, right - left + 1)  # Update min length
                window_sum -= nums[left]  # Remove left end element
                left += 1                # Move left pointer right, shrink window

        # If no subarray meeting the conditions is found, return 0
        return 0 if min_len == float('inf') else min_len

javascript

const minSubArrayLen = function(target, nums) {
    let left = 0;
    let minLen = Infinity;
    let windowSum = 0;

    for (let right in nums) {
        windowSum += nums[right];
        while (windowSum >= target) {
            minLen = Math.min(minLen, right - left + 1)
            windowSum -= nums[left];
            left += 1;
        }
    }

    return minLen === Infinity ? 0 : minLen;
}

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

209. Minimum Size Subarray Sum (English)209. 长度最小的子数组 (Chinese)