LeetCode 209: Minimum Size Subarray Sum (Sliding Window)
LeetCode 209ArrayTwo PointersSliding WindowToday we solve LeetCode 209 - Minimum Size Subarray Sum.
Source: https://leetcode.com/problems/minimum-size-subarray-sum/
English
Problem Summary
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray whose sum is at least target. If no such subarray exists, return 0.
Key Insight
Because all numbers are positive, expanding the right pointer only increases (or keeps) the window sum, and moving the left pointer decreases it. This monotonic behavior enables a linear-time sliding window.
Brute Force and Limitations
Brute force checks every start index and accumulates forward until reaching target. Worst-case complexity is O(n²), which is too slow for large inputs.
Optimal Algorithm Steps
1) Initialize left = 0, sum = 0, and best = +∞.
2) Iterate right from left to right, adding nums[right] to sum.
3) While sum >= target, update best = min(best, right-left+1), then subtract nums[left] and move left to shrink the window.
4) Continue until traversal finishes; return 0 if best is unchanged.
Complexity Analysis
Time: O(n), each pointer moves at most n times.
Space: O(1).
Common Pitfalls
- Forgetting the positivity constraint (this exact method does not work with negative numbers).
- Updating answer only once per right expansion instead of shrinking fully in a while loop.
- Off-by-one when computing length right-left+1.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int best = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= nums[left++];
}
}
return best == Integer.MAX_VALUE ? 0 : best;
}
}func minSubArrayLen(target int, nums []int) int {
left, sum := 0, 0
best := int(^uint(0) >> 1)
for right := 0; right < len(nums); right++ {
sum += nums[right]
for sum >= target {
if right-left+1 < best {
best = right - left + 1
}
sum -= nums[left]
left++
}
}
if best == int(^uint(0)>>1) {
return 0
}
return best
}class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0, sum = 0;
int best = INT_MAX;
for (int right = 0; right < (int)nums.size(); ++right) {
sum += nums[right];
while (sum >= target) {
best = min(best, right - left + 1);
sum -= nums[left++];
}
}
return best == INT_MAX ? 0 : best;
}
};class Solution:
def minSubArrayLen(self, target: int, nums: list[int]) -> int:
left = 0
window_sum = 0
best = float("inf")
for right, x in enumerate(nums):
window_sum += x
while window_sum >= target:
best = min(best, right - left + 1)
window_sum -= nums[left]
left += 1
return 0 if best == float("inf") else bestvar minSubArrayLen = function(target, nums) {
let left = 0;
let sum = 0;
let best = Number.POSITIVE_INFINITY;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= nums[left++];
}
}
return Number.isFinite(best) ? best : 0;
};中文
题目概述
给定正整数数组 nums 和正整数 target，求和至少为 target 的最短连续子数组长度；若不存在，返回 0。
核心思路
由于数组元素都为正数，右指针右移时窗口和只会增大，左指针右移时窗口和只会减小。这个单调性让我们可以用滑动窗口在线性时间内完成搜索。
朴素解法与不足
朴素做法是枚举每个起点并向右累加直到达到 target，最坏需要 O(n²)，在大输入下会超时。
最优算法步骤
1）初始化 left = 0、sum = 0、best = +∞。
2）遍历右指针 right，将 nums[right] 加入窗口和。
3）当 sum >= target 时，先更新最短长度，再不断右移左指针收缩窗口。
4）遍历结束后，若 best 未更新则返回 0，否则返回 best。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。
常见陷阱
- 忽略“元素全为正数”的前提（有负数时此方法不成立）。
- 只在每次扩张后更新一次答案，没有在 while 中持续收缩。
- 子数组长度写错，必须是 right-left+1。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int best = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= nums[left++];
}
}
return best == Integer.MAX_VALUE ? 0 : best;
}
}func minSubArrayLen(target int, nums []int) int {
left, sum := 0, 0
best := int(^uint(0) >> 1)
for right := 0; right < len(nums); right++ {
sum += nums[right]
for sum >= target {
if right-left+1 < best {
best = right - left + 1
}
sum -= nums[left]
left++
}
}
if best == int(^uint(0)>>1) {
return 0
}
return best
}class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0, sum = 0;
int best = INT_MAX;
for (int right = 0; right < (int)nums.size(); ++right) {
sum += nums[right];
while (sum >= target) {
best = min(best, right - left + 1);
sum -= nums[left++];
}
}
return best == INT_MAX ? 0 : best;
}
};class Solution:
def minSubArrayLen(self, target: int, nums: list[int]) -> int:
left = 0
window_sum = 0
best = float("inf")
for right, x in enumerate(nums):
window_sum += x
while window_sum >= target:
best = min(best, right - left + 1)
window_sum -= nums[left]
left += 1
return 0 if best == float("inf") else bestvar minSubArrayLen = function(target, nums) {
let left = 0;
let sum = 0;
let best = Number.POSITIVE_INFINITY;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
best = Math.min(best, right - left + 1);
sum -= nums[left++];
}
}
return Number.isFinite(best) ? best : 0;
};
Comments