Problem Statement

Subarray Sum Equals K

You are given a list of numbers called nums and a target number k. A subarray is just a chunk of numbers sitting next to each other in the list, with no gaps. Your job is to count how many of these chunks add up to exactly k. The slow way is to try every possible chunk and add each one up, which is O(n^2), meaning the work grows with the square of the list size. The fast way uses two ideas working together. First, a running total called a prefix sum, which is the sum of everything from the start of the list up to where you are right now. Second, a hash map, which is like a tally sheet where you write down a value and how many times you have seen it, and you can look any value up instantly. Here is the trick that ties them together. If the prefix sum at position j minus the prefix sum at an earlier position i equals k, then the chunk of numbers between those two spots adds up to k. So at each spot j, you ask: how many earlier prefix sums were exactly (current prefix sum minus k)? The tally sheet answers that in one step, O(1).

mediumArrayHash TableArrays & HashingTime: O(n) · Space: O(n)

Signals to notice

count subarrays summing to knot necessarily positiveprefix sum + hash map

Brute force first

Check every subarray sum. Each subarray independently summed. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Prefix sums + hash map: for each position, compute the prefix sum. If prefixSum - k exists in the map, that many subarrays ending here sum to k. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `nums=[1,2,3], k=3`

init: map={0:1}, sum=0, count=0
num=1: sum=1, need 1-3=-2 (absent, +0), count=0, map={0:1,1:1}
num=2: sum=3, need 3-3=0 (freq 1), count=1, map={0:1,1:1,3:1}
num=3: sum=6, need 6-3=3 (freq 1), count=2, map={0:1,1:1,3:1,6:1}
loop ends -> return count=2 (subarrays [1,2] and [3])

What must stay true

sum(i.j) = prefixSum[j] - prefixSum[i-1]. If prefixSum[j] - k = prefixSum[i-1], then the subarray from i to j sums to k. The hash map counts how many previous prefix sums equal prefixSum[j] - k. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

map = {0: 1}; sum = 0; count = 0
for num in nums:
    sum += num
    count += map.get(sum - k, 0)   # subarrays ending here
    map[sum] = map.get(sum, 0) + 1
return count

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Trying sliding window — that only works for positive numbers. With negatives or zeros, use prefix sums. Also, initialize the map with {0: 1} for subarrays starting at index 0. The fix is usually to return to the meaning of each move, not just the steps themselves.

Arrays & Hashing Pattern