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
- Counting subarrays with exactly
goalones is awkward directly, but counting those with at mostgoalones is a clean sliding window. - Define
atMost(g): the window is valid while its sum is at mostg, and each right endpoint contributesr - l + 1subarrays (all start positions in the valid window). - Then the answer is
atMost(goal) - atMost(goal - 1). - 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 < 0guard:atMost(-1)must be 0, otherwise the window logic breaks on thegoal = 0case. - 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.
🧩 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