Binary Subarrays With Sum

1. The "Exactly Goal" = "At Most Goal" minus "At Most Goal-1" Trick

• Counting subarrays with exactly a given sum directly with a sliding window is difficult.
• Instead, compute: atMost(goal) - atMost(goal - 1).
• atMost(goal) counts all subarrays with sum 0, 1, 2, ..., or goal.
• Subtracting atMost(goal - 1) removes subarrays with a sum less than goal, leaving exactly those with sum equal to goal.

2. The atMost Helper

• If g < 0, return 0 immediately (no valid subarrays possible).
• Initialize left = 0, sum = 0 (running sum of the window), and count = 0.
• Iterate right across the array. Add nums[right] to sum.

3. Shrink When Sum Exceeds Goal

• While sum > g, subtract nums[left] from sum and increment left.
• This contracts the window until the sum is within the allowed limit.

4. Count Valid Subarrays

• After adjusting, every subarray ending at right and starting from any index in [left, right] has sum at most g.
• Add right - left + 1 to count.

5. Combine the Results

• Return atMost(goal) - atMost(goal - 1) for the final answer.

🧠 Key Insight

The atMost subtraction pattern is essential for "exactly K" problems on binary arrays. Since all values are 0 or 1, the sum increases monotonically as the window expands, which is exactly the property needed for the sliding window to work correctly. The solution runs in O(n) time (two linear passes) and O(1) space. The g < 0 guard in atMost handles the edge case where goal = 0 elegantly, since atMost(-1) returns 0.