Minimum Size Subarray Sum
Problem
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
target = 7, nums = [2, 3, 1, 2, 4, 3]2def min_sub_array_len(target, nums):
l = sum_ = 0
best = float("inf")
for r in range(len(nums)):
sum_ += nums[r]
while sum_ >= target:
best = min(best, r - l + 1)
sum_ -= nums[l]
l += 1
return 0 if best == float("inf") else bestfunction minSubArrayLen(target, nums) {
let l = 0, sum = 0, best = Infinity;
for (let r = 0; r < nums.length; r++) {
sum += nums[r];
while (sum >= target) {
best = Math.min(best, r - l + 1);
sum -= nums[l++];
}
}
return best === Infinity ? 0 : best;
}class Solution {
public int minSubArrayLen(int target, int[] nums) {
int l = 0, sum = 0, best = Integer.MAX_VALUE;
for (int r = 0; r < nums.length; r++) {
sum += nums[r];
while (sum >= target) {
best = Math.min(best, r - l + 1);
sum -= nums[l++];
}
}
return best == Integer.MAX_VALUE ? 0 : best;
}
}int minSubArrayLen(int target, vector<int>& nums) {
int l = 0, sum = 0, best = INT_MAX;
for (int r = 0; r < (int)nums.size(); r++) {
sum += nums[r];
while (sum >= target) {
best = min(best, r - l + 1);
sum -= nums[l++];
}
}
return best == INT_MAX ? 0 : best;
}Explanation
We want the shortest run of numbers that adds up to at least target. Because every number is positive, growing a window only ever makes the sum bigger, and shrinking it only ever makes the sum smaller. That clean behavior is what lets a sliding window work.
We keep a window between two pointers, l (left) and r (right). We move r forward one step at a time and add nums[r] to a running sum_.
Whenever sum_ reaches target, the window is valid, so we record its length r - l + 1 if it beats our best. Then we try to make it even shorter by dropping nums[l] and moving l right, repeating while the sum is still big enough.
Example: nums = [2, 3, 1, 2, 4, 3], target = 7. The window grows to [2,3,1,2] (sum 8), then we shrink from the left until it no longer reaches 7. Later the window [4,3] hits sum 7 with length 2, which is the answer.
Each pointer only ever moves forward, so we touch every element a constant number of times — that is why this runs in one pass. If no window ever reaches the target, best stays at infinity and we return 0.