Prefix Sums — Subarray Sum Equals K

Return how many contiguous subarrays of nums add up to exactly k.

nums may contain negative numbers and zeros, so a sliding window does not
work: growing a window can make its sum go down. Use prefix sums instead. The
sum of nums[i..j] is prefix[j + 1] - prefix[i], so a subarray ending at
j sums to k exactly when an earlier prefix equals prefix[j + 1] - k.
Count earlier prefixes in a hash map and the answer comes in one O(n) pass.

Examples

solve([1, 1, 1], 2)    → 2   // [1, 1] twice
solve([1, 2, 3], 3)    → 2   // [1, 2] and [3]
solve([1, -1, 0], 0)   → 3   // [1, -1], [0], [1, -1, 0]

Constraints

• 1 <= nums.length <= 20000
• -1000 <= nums[i] <= 1000, -10^7 <= k <= 10^7