286. How Many Subarrays Add Up to K
Print how many contiguous subarrays sum to exactly k. Values may be
negative, so a running total is not monotonic and a sliding window will not
work.
The technique is prefix sums. Let S(i) be the total of the first i
values. Then the subarray from i to j sums to S(j) - S(i), so asking
for a subarray summing to k ending at j is asking how many earlier
prefixes equal S(j) - k.
That is a lookup, so keep a map from prefix sum to how many times it has occurred. The map must start containing the sum 0 once, standing for the empty prefix, or every subarray starting at index 0 is missed.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ k ≤ 1000000000` - `-1000 ≤ a[i] ≤ 1000`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print one integer, the number of contiguous subarrays summing to k.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.