Why it works
- The sum of a subarray is the running sum at its end minus the running sum before its start. So a subarray ending here adds up to k exactly when an earlier prefix equals prefix − k, and seen says how many such prefixes there were.
- seen starts with {0: 1}, the empty prefix before index 0. Without it, [1, 2] and [1, 2, -1, 3, -2], which start at index 0, would never be counted.
- Negative numbers break a sliding window: the sum drops and grows again, as in [1, 2, -1, 3, -2]. A difference of prefixes does not care about signs.
Complexity
Time O(n): one pass, and a map lookup or update takes O(1) on average. Memory O(n): seen may hold n + 1 different prefixes.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗