Description Link to heading
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
Constraints:
1 <= target <= 10⁹1 <= nums.length <= 10⁵1 <= nums[i] <= 10⁴
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)).
Solution Link to heading
sliding window Link to heading
If sum < target, then we let right pointer moves to the right, sum += nums[right++], we enlarge the window; Otherwise, we update min_len, make left pointer moves to the right, sum -= nums[left], narrow the window.
prefix sum + binary search Link to heading
Since we need consider the sum of the subarrays, we can use prefix sum, which is monotonically increasing. So we can use binary search to find the maximum i that satisfies prefix[j] - prefix[i] >= target. The answer to the problem is $(j - i)_{\min}$.
Code Link to heading
sliding window Link to heading
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0, right = 0;
int sum = 0;
int min_len = nums.size() + 1;
while (right < nums.size()) {
while (sum < target && right < nums.size()) {
sum += nums[right++];
}
while (sum >= target && left <= right) {
if (sum >= target) {
min_len = min(min_len, right - left);
}
sum -= nums[left];
left++;
}
}
if (min_len > nums.size()) {
return 0;
}
return min_len;
}
};
prefix sum + binary search Link to heading
class Solution {
public:
int BSearch(int idx, int target, vector<int> &prefix) {
int left = 0, right = idx;
while (left < right) {
int mid = left + (right - left) / 2;
if (prefix[mid] < prefix[idx] - target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
int minSubArrayLen(int target, vector<int> &nums) {
int n = nums.size();
vector<int> prefix(n + 1, 0);
for (int i = 1; i <= nums.size(); i++) {
prefix[i] = prefix[i - 1] + nums[i - 1];
}
int res = n + 1;
for (int i = 1; i <= n; i++) {
int j = BSearch(i, target - 1, prefix);
if (prefix[i] >= target) {
res = std::min(i - j + 1, res);
}
}
if (res == n + 1) {
return 0;
}
return res;
}
};