Subarrays with exactly k total

Problem

A hostel mess wallet records the net money change for each of n days. Money added is positive, money spent is negative, and a quiet day is 0.

Count the stretches of one or more consecutive days whose total change is exactly k.

Input: The first line has two integers n and k. The second line has n integers: the change for each day, in order.
Output: One integer: the number of stretches with a total of exactly k.
Constraints: 1 ≤ n ≤ 10^5
−10^9 ≤ change ≤ 10^9
−10^14 ≤ k ≤ 10^14

Example 1

Input

5 3
1 2 1 2 1

Output

Days 1–2, 2–3, 3–4 and 4–5 each add up to 3.

Example 2

Input

6 0
3 -3 2 -2 0 1

Output

With negative values, many stretches can cancel out to 0.

Try the problem first. Open one hint at a time.

Hint 1

Because values can be negative, a growing and shrinking window does not work here.

Hint 2

Let total be the sum of days 1 to j. A stretch ending at day j adds up to k when an earlier running total equals total - k.

Hint 3

Keep a HashMap from each running total to how many times it has appeared so far.

Hint 4

Put total 0 in the map once before you start: it stands for "before day 1", so stretches that start on day 1 are counted.

Write your Java code, run it on the examples and submit it to hidden tests.