209. Minimum Size Subarray Sum 🔗
Date: Jun 02, 2024
Tags: two-pointers, sliding-window
Description
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 <= 109 -
1 <= nums.length <= 105 -
1 <= nums[i] <= 104
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)).
Optimal
function minSubArrayLen(target: number = 0, nums: number[]): number {
let left = 0;
let total = 0;
let result = Infinity;
for (let right = 0; right < nums.length; right++) {
total += nums[right];
while (total >= target) {
result = Math.min(result, right - left + 1);
total -= nums[left];
left++;
}
}
return result === Infinity ? 0 : result;
}
export { minSubArrayLen };
Brute-Force
function minSubArrayLen(target: number, nums: number[]): number {
const answers: number[] = [];
for (let x = 0; x < nums.length; x++) {
let acc = 0;
for (let y = x; y < nums.length; y++) {
if (x === y) acc = nums[x];
else acc += nums[y];
if (acc >= target) {
answers.push(Math.abs(y - x) + 1);
break;
}
}
}
return answers.length ? Math.min(...answers) : 0;
}
export { minSubArrayLen };
