Subarray Sum Equals K

What it tests

The prefix-sum + hash-map combo. Sliding window fails here because values can be negative.

Approach & answer

Running sum `sum`. A subarray ending at i sums to k exactly when a previous prefix equalled `sum − k`. Store how many times each prefix sum has occurred; add that count. Seed the map with {0: 1} so subarrays starting at index 0 are counted. Note: sliding window doesn't work with negatives — growing the window can decrease the sum, so there's no monotonic 'shrink when too big' invariant. That's the trap this problem sets, and the reason the prefix-sum + hash-map combo is the right reach.

Use this technique when

'How many subarrays sum to K' (especially with negatives) → prefix sums counted in a hash map.

Complexity

Time O(n) · Space O(n)

References

• LeetCode 560 · Subarray Sum Equals K