Subarray Sum Equals K

Count the contiguous, non-empty subarrays whose sum is exactly k. Numbers can be negative.

Input:

• line 1: n k
• line 2: n integers

Output: the number of such subarrays (it may need a 64-bit integer).

Constraints: 1 ≤ n ≤ 10⁵, −1000 ≤ a[i] ≤ 1000, −10⁷ ≤ k ≤ 10⁷.

Think about it: the sum of a[i..j] is prefix[j] − prefix[i−1]. Keep a hash map of how many times each prefix sum has appeared. (A sliding window does not work here — why?)