AlgoViz
HomePrefix Sum

Subarray Sum Equals K

Medium

Running prefix + a count hashmap

In simple words

Track running totals; if you've seen (current total − k) before, a chunk in between adds up to k.

The idea

If two prefix sums differ by k, the slice between them sums to k. Keep a map of prefix-sum frequencies and, at each step, add how many earlier prefixes equal current − k.

1
1
1
2
1
0
1
2
3
4
target2

Step 1 of 17. Brute force: add up every subarray, count those summing to 2. Values: 1, 1, 1, 2, 1. target 2.

1/17
Brute force
timeO(n²)spaceO(1)

Sum every subarray.

1// add up every subarray, count the ones equal to k2for (let i = 0; i < n; i++) {3  let sum = 0;4  for (let j = i; j < n; j++) { sum += nums[j]; if (sum === k) count++; }5}

Input

array
[1, 1, 1, 2, 1]

Memory

target
2

Output

count
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 1, 1], k = 2
Output:
2
Explanation:
Two windows [1,1] each sum to 2.

Example 2

Input:
nums = [1, 2, 3], k = 3
Output:
2
Explanation:
[3] and [1,2] both total 3.

Example 3

Input:
nums = [0, 0, 0], k = 0
Output:
6
Explanation:
Every window of 0s sums to 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.