NeetCode #238LC-209MediumSliding WindowNC 250
← Back to All Problems#238 · #209 · Minimum Size Subarray Sum(长度最小的子数组)
📌 Problem Statement & Constraints
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 none exists, return 0. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^4, 1 <= target <= 10^9.💡 Core Algorithmic Approaches
- All values are positive, so the window sum is monotone in both directions -- a sliding window applies.
- Expand the right end, adding to the running sum.
- While the sum is at least
target, record the window length and shrink from the left. - Because the sum only decreases when shrinking, the inner loop is amortised O(n) overall.
💻 Benchmark Python3 Implementation
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
l = 0
cur = 0
best = float("inf")
for r, x in enumerate(nums):
cur += x
while cur >= target: # valid -> try to shrink
best = min(best, r - l + 1)
cur -= nums[l]
l += 1
return best if best != float("inf") else 0⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each element enters and leaves the window at most once.
💾 Space Complexity
O(1): three scalars.
⚠️ Interview Pitfalls & Follow-ups
- Using this approach with negative numbers: the monotonicity of the window sum is what makes it valid, and the constraints guarantee positivity. For general values, prefix sums with a hash map are needed.
- Using
> targetinstead of>=: the requirement is *at least*target. - Returning
bestwhen no window qualifies: it would beinf; the sentinel check converts it to 0. - Shrinking only once instead of in a
whileloop: the minimal window requires shrinking as far as possible.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner