Subarray Sum Equals K - Classic Problems | Repovive

CLS45. Subarray Sum Equals K

2s256 MB

Given an array of integers and a target value $k$ , count the number of non-empty contiguous subarrays whose sum is exactly $k$ .

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

count

Input

5 3
1 2 1 2 1

Explanation

There are four contiguous subarrays with total 3: positions 1..2, 2..3, 3..4, and 4..5.

Output

Input

4 0
0 0 0 0

Explanation

Every non-empty contiguous subarray has total 0, so all 10 subarrays count.

Output

Input

6 -1
2 -3 1 -1 2 -2

Explanation

The six qualifying segments are 1..2, 1..4, 1..6, 2..5, 4..4, and 4..6.

Output

Given an array of integers and a target value $k$ , count the number of non-empty contiguous subarrays whose sum is exactly $k$ .

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

count