visual walkthrough
Binary Subarrays With Sum
Introduces the 'exactly = at most − at most' trick.
The idea
A sliding window handles "at most" limits neatly, because shrinking always reduces the sum. "Exactly goal" isn't monotonic, but it equals (subarrays with sum ≤ goal) minus (subarrays with sum ≤ goal − 1).
Each count is one linear pass with the add-then-count-the-window trick.
Complexity
| approach | time | space |
|---|---|---|
| Try every subarray | O(n²) | O(1) |
| atMost(k) − atMost(k−1) | O(n) | O(1) |