⚡Flashcard Drill➔
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

  1. All values are positive, so the window sum is monotone in both directions -- a sliding window applies.
  2. Expand the right end, adding to the running sum.
  3. While the sum is at least target, record the window length and shrink from the left.
  4. 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 > target instead of >=: the requirement is *at least* target.
  • Returning best when no window qualifies: it would be inf; the sentinel check converts it to 0.
  • Shrinking only once instead of in a while loop: 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems