ArrayPrefix SumHash Map
Count the contiguous subarrays whose elements add up to exactly k. The array can contain negative numbers, so a sliding window will not work.
Input
Line 1: n and k. Line 2: n integers.
Output
Print the number of subarrays with sum k.
Constraints
1 <= n <= 2 * 10^4 -1000 <= each value <= 1000 -10^7 <= k <= 10^7
Example 1
Input
3 2 1 1 1
Output
2
Two subarrays of length 2 sum to 2.
Example 2
Input
4 3 1 2 3 -3
Output
3
The subarrays [1, 2], [3] and [1, 2, 3, -3] each sum to 3.