Minimum Size Subarray Sum
Given an array of integers `nums` and an integer `s`, return the length of the shortest subarray that contains at least one integer that sums up to `s`. If no such subarray exists, return 0.
Constraints:
- 1 <= nums.length <= 10^5
- 1 <= s <= 10^9
- -10^5 <= nums[i] <= 10^5
Examples:
Input: [2,3,1,2,4,3], s = 7
Output: 2
Explanation: The subarray [4,3] has the minimum length of 2 and sums up to 7.
Solutions
Two Pointers
Time: O(n)Space: O(1)
We use two pointers, `left` and `right`, to represent the sliding window. We keep adding elements to the window until the sum is greater than or equal to `s`. Then, we try to minimize the window by moving the `left` pointer to the right. We keep track of the minimum length of the subarray that sums up to `s`.
def minSubArrayLen(s, nums):
left, curr_sum, min_len = 0, 0, float('inf'); for right in range(len(nums)):
curr_sum += nums[right]; while curr_sum >= s:
min_len = min(min_len, right - left + 1); curr_sum -= nums[left]; left += 1; return 0 if min_len == float('inf') else min_lenFollow-up:
What if the array contains negative numbers?
