Subarray Sum Equals K

Turn every contiguous range into a difference between two prefix sums. As you scan, ask whether the prefix you need has already appeared.

The memory hook

Count the prefix you need before recording the prefix you have.

MediumPrefix sum + hash mapO(n) timeO(n) space

Why prefix sums count ranges

intuition

Let prefix[i] be the sum through index i. A subarray ending here sums to k exactly when an earlier prefix equals current - k. The map remembers how many earlier starting points can make that equation true.

1AccumulateAdd the next number to get the current prefix sum at the right edge of a candidate range.

2Look backAsk for current prefix − k. Every occurrence is a different subarray start.

3RecordOnly after counting matches, add the current prefix to the map so a range cannot use an empty or future prefix.

The invariant: before processing the next element, the map contains the frequency of every prefix sum ending strictly before it. That makes each lookup count all valid starts exactly once.

Watch the prefixes meet

playable trace

Try the canonical [1, 1, 1] with k = 2. The trace exposes the needed prefix, the map of earlier frequencies, and the running answer.

Playable trace · prefix frequency map

Frames use the same lookup-before-insert order as the code below.

target k

Presets

Current event

Ready — press Play

Subarrays found

prefix map · sum → count

Start with prefix sum 0 occurring once: the empty prefix gives a subarray that starts at index 0.

unread current processed matching prefix

0 / 0 speed 650ms

Lookup first, then insert

the solution

Python · prefix sums + frequency map

def subarraySum(nums, k):
    frequencies = {0: 1}  # empty prefix before index 0
    prefix = answer = 0

    for value in nums:
        prefix += value
        answer += frequencies.get(prefix - k, 0)
        frequencies[prefix] = frequencies.get(prefix, 0) + 1

    return answer

The initial {0: 1} represents the prefix before the array. It is what counts a valid range beginning at index 0.

Current prefixS[j]Sum through the current right endpoint j.

Needed prefixS[j] − kAn earlier prefix with this value makes the difference exactly k.

Frequencycount[S[j] − k]Each occurrence is one distinct left boundary, so add the count rather than just one.

Why does the order matter? Lookup happens before insertion. The map therefore contains only prefixes from earlier positions, and the current prefix cannot form a zero-length subarray with itself.

TimeO(n)one hash lookup and one update per element

SpaceO(n)at most one frequency entry per distinct prefix sum

Two quick mental checks

make it stick

nums = [1, 1, 1], k = 2

Answer = 2

The prefix sequence is 0, 1, 2, 3. At prefix 2, the needed value is 0; at prefix 3, it is 1, which has appeared once. Those are the two length-2 windows.

nums = [1, -1, 0], k = 0

Answer = 3

Repeated prefix sums are useful: prefix 0 appears before the array, after [1,-1], and after the final 0. Their frequencies count all three valid subarrays.

What to say out loud

“I represent a subarray sum as the difference of two prefix sums. While scanning, I keep frequencies of prefixes from earlier positions. For the current sum S, every earlier S minus k gives one valid start, so I add that frequency before recording S. This counts each range once in linear time.”