⚡Flashcard Drill➔
NeetCode #243LC-930MediumSliding Window
← Back to All Problems

#243 · #930 · Binary Subarrays With Sum(和相同的二元子数组)

📌 Problem Statement & Constraints

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum equal to goal. Constraints: 1 <= nums.length <= 3 * 10^4, 0 <= goal <= nums.length.

💡 Core Algorithmic Approaches

  1. Counting subarrays with exactly goal ones is awkward directly, but counting those with at most goal ones is a clean sliding window.
  2. Define atMost(g): the window is valid while its sum is at most g, and each right endpoint contributes r - l + 1 subarrays (all start positions in the valid window).
  3. Then the answer is atMost(goal) - atMost(goal - 1).
  4. This "exactly k = at most k minus at most k-1" pattern is a general technique worth remembering.

💻 Benchmark Python3 Implementation

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        def atMost(g: int) -> int:
            if g < 0:
                return 0               # no subarray can have a negative sum
            l = 0
            cur = 0
            res = 0
            for r, x in enumerate(nums):
                cur += x
                while cur > g:
                    cur -= nums[l]
                    l += 1
                res += r - l + 1       # all starts in the window are valid
            return res

        return atMost(goal) - atMost(goal - 1)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): two linear passes, since each pointer moves monotonically within each call.
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using a plain sliding window for the exact count: the window is not uniquely determined by "sum == goal" at each right endpoint, so the subtraction trick is needed.
  • Forgetting the g < 0 guard: atMost(-1) must be 0, otherwise the window logic breaks on the goal = 0 case.
  • Using prefix sums with a hash map: also correct and O(n) space, but the two-pass window is simpler and uses O(1) space.
  • Adding 1 instead of r - l + 1: every valid start position contributes a distinct subarray.
⚡
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