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`.
int minSubArrayLen(int s, vector<int>& nums) {
int left = 0, sum = 0, minLen = INT_MAX;
for (int right = 0;
right < nums.size();
right++) {
sum += nums[right];
while (sum >= s) {
minLen = min(minLen, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLen == INT_MAX ? 0 : minLen;
}Follow-up:
What if the array contains negative numbers?
