Binary Subarrays With Sum
Given a binary array nums and an integer goal, count the number of non-empty subarrays whose sum equals goal.
Intuition
Counting subarrays with sum exactly goal is awkward, but counting subarrays with sum at most k slides cleanly. Then exactly(goal) = atMost(goal) − atMost(goal − 1).
Approach
Counting exact sums directly is awkward
Brute force sums every subarray and tallies the ones equal to goal — O(n²). A sliding window seems natural, but it struggles with exact sums: when the window sum equals the goal, you can't simply decide whether to grow or shrink, because a 0 at either edge keeps the sum the same. The window technique wants a monotonic condition.
Reframe 'exactly' as a difference of 'at most'
The clean, monotonic version is atMost(k) = the number of subarrays whose sum is ≤ k — that does slide nicely. Then the answer is atMost(goal) − atMost(goal − 1): every subarray summing to ≤ goal, minus every subarray summing to ≤ goal−1, leaves precisely those summing to exactly goal. Trading one hard count for two easy ones is the whole trick.
Implement atMost as a standard window
For atMost(k): expand right, adding to a running sum; whenever the sum exceeds k, shrink from left until it's valid again. At each right, every subarray ending there and starting anywhere in [left, right] is valid, contributing right − left + 1 to the count. Call it twice and subtract. Two linear passes — O(n) time, O(1) space.
Solution & live demo
Edge cases
atMost(-1) returns 0, so the answer is atMost(0) — runs of consecutive zeros, counted correctly.
Only the full array qualifies; the window math yields exactly 1.
The two atMost counts are equal, so their difference is 0.