visual walkthrough
Subarray Sum Equals K
The canonical 'count prefixes equal to sum − k' problem; appears everywhere.
The idea
The sum of the numbers between two positions is the difference of two running totals. So a subarray ending here adds up to k exactly when an earlier running total equals (total now − k).
Keep a map of how many times each running total has appeared, and every position can count its matching subarrays in one lookup.
Complexity
| approach | time | space |
|---|---|---|
| Try every subarray | O(n²) | O(1) |
| Prefix sums + map | O(n) | O(n) |