Subarrays Summing to K

Difficulty: 1500 2000 ms 128 MB

prefix-sums

Count the contiguous subarrays whose sum equals K. Values may be negative, so sliding windows do not work.

Input: the first line has N and K; the second line has N integers.

Output: the number of subarrays with sum K.

Constraints:

• 1 ≤ N ≤ 10⁵
• −10⁴ ≤ a_i, K ≤ 10⁴

Sample Tests

5 3
1 2 3 -2 2

4

3 0
1 -1 1

2

Read the Editorial