The problem
Count the number of contiguous subarrays whose elements sum to exactly k. Values may be negative.
Stuck? Reveal hints one at a time
How to approach it
- 1Maintain running prefix sum and a map {prefixValue → occurrences}, seeded with {0: 1}.
- 2For each element: prefix += value.
- 3Add map[prefix − k] (0 if absent) to the answer — each such earlier prefix starts a valid subarray ending here.
- 4Increment map[prefix].
Key insight
Seeding {0: 1} counts subarrays that start at index 0 — the "empty prefix" is a real prefix, and forgetting it silently drops answers.
The solution
Watch out for
- Update the map AFTER counting — otherwise a subarray of length 0 can match when k = 0.
- Sliding window is a trap here; it requires non-negative values.