Prefix Sums and Hash Maps: Solving 'Subarray Sum Equals K'

Subarray Sum Equals K is a very useful problem because it looks like a sliding‑window question right up until it suddenly is not. We are given an array and a target sum, and we need to count how many contiguous subarrays add up to that target.

At first glance, it feels as if two pointers should be enough. Keep a running sum, expand when the total is too small, shrink when it is too big, and carry on. That works beautifully in some array problems.

It does not work here once negative numbers are allowed.

That is the real lesson. This is not primarily a window problem. It is a prefix‑sum problem.

Why Sliding Window is the Wrong Instinct

Sliding window depends on a kind of monotonic behaviour. If all values were non‑negative, then:

• moving right would only increase the sum
• moving left would only decrease the sum

That would make the window easy to steer.

But if the array can contain negatives, the sum stops behaving that neatly. Expanding the window can make the total smaller. Shrinking it can make the total larger. The usual left‑right pointer logic loses its grip.

That is why this problem is such a good separator. It teaches when not to use a fashionable pattern.

The Brute‑Force Version is Easy to Trust

The most obvious answer is:

• pick every starting index
• extend forwards
• keep a running total
• increment the answer whenever the total hits k

export const subarraySum = (values: number[], target: number): number => {  let count = 0;  for (let start = 0; start < values.length; start += 1) {    let total = 0;    for (let end = start; end < values.length; end += 1) {      total += values[end];      if (total === target) {        count += 1;      }    }  }  return count;};

This is not a bad teaching version. It keeps the sums incremental rather than recalculating them from scratch, and it makes the problem definition very concrete.

It is still O(n^2), though, which is more work than we need.

The Prefix‑Sum Reframing

The better way to think about the problem is:

• let prefixSum be the sum of everything up to the current index

If a subarray from start to end sums to k, then:

prefixSum[end] - prefixSum[start - 1] = k

Rearrange that, and we get:

prefixSum[start - 1] = prefixSum[end] - k

That means when we are standing at index end, the real question is not:

• can I grow or shrink a window?

It is:

• how many earlier prefix sums were equal to currentPrefixSum ‑ k?

That is a very different shape of solution.

The Map solution

export const subarraySum = (values: number[], target: number): number => {  const prefixCounts = new Map<number, number>();  prefixCounts.set(0, 1);  let prefixSum = 0;  let count = 0;  for (const value of values) {    prefixSum += value;    count += prefixCounts.get(prefixSum - target) ?? 0;    prefixCounts.set(      prefixSum,      (prefixCounts.get(prefixSum) ?? 0) + 1    );  }  return count;};

Why prefixCounts.set(0, 1) matters so much

This is the line that often looks a bit arbitrary until the first example is traced properly.

It means:

• before we have processed any values, we have seen one prefix sum of 0

That allows subarrays starting at index 0 to be counted correctly.

If the running prefix sum itself becomes k, then:

prefixSum - target = 0

and the map tells us there is one valid earlier prefix sum to pair with it: the empty prefix before the array started.

Without that initial 0 ‑> 1, those front‑of‑array matches are missed.

Walking through a Small Example

Take:

values = [1, 1, 1]target = 2

Start with:

prefixCounts = { 0: 1 }prefixSum = 0count = 0

Process the first 1:

• prefixSum = 1
• look for 1 ‑ 2 = ‑1
• not found
• store prefix sum 1

Process the second 1:

• prefixSum = 2
• look for 2 ‑ 2 = 0
• found once
• count = 1
• store prefix sum 2

Process the third 1:

• prefixSum = 3
• look for 3 ‑ 2 = 1
• found once
• count = 2

The two counted subarrays are:

• [1, 1] from indices 0..1
• [1, 1] from indices 1..2

That is the important thing to notice. The map is not storing subarrays directly. It is storing how many ways the current prefix sum could pair with an earlier prefix sum to produce the target difference.

Why the Map Stores Counts, Not Just Existence

This is another easy mistake.

If a particular prefix sum has appeared more than once, then the current index may complete more than one valid subarray. So we do not want:

• have we seen this prefix sum?

We want:

• how many times have we seen this prefix sum?

That is why the map value is a count rather than a boolean.

For example, in arrays with zeros or repeated running totals, the same prefix sum can recur. Each previous occurrence represents a different starting point for a valid subarray ending here.

Comparing the Two Solutions Honestly

The nested‑loop answer is fine when:

• we are proving the problem to ourselves
• the input is tiny
• we want the simplest possible first draft

The prefix‑sum map answer is clearly better for the real problem:

• O(n) time instead of O(n^2)
• handles negative values cleanly
• scales without repeated rescanning

So unlike some LeetCode questions where there are two equally good editorial angles, this one is more decisive. The brute‑force answer is useful for understanding. The prefix‑sum answer is the one worth keeping.

Why This Pattern Shows up so Often

This is a strong general pattern because many array questions can be reframed in terms of:

• the running total so far
• some earlier running total we need to have seen already

Once that click happens, the hash map starts to feel less like a trick and more like a ledger of earlier states we can pair with the present one.

That is why this pattern turns up in problems involving:

• target sums
• divisible totals
• balanced counts after converting values into +1 and ‑1

Common Mistakes

Reaching for Sliding Window Automatically

Negative numbers break the monotonic behaviour that sliding windows rely on.

Forgetting to seed the map with 0 ‑> 1

That drops valid subarrays that start at the beginning of the array.

Storing Only Whether a Prefix Sum Exists

The same prefix sum can occur multiple times, and every occurrence matters.

The Main Thing Worth Remembering

The decisive move in Subarray Sum Equals K is not "keep a window". It is:

• convert the subarray question into a difference between two prefix sums

Once we do that, the hash map becomes the natural data structure.

The Pattern to Keep

• Sliding window is not the right tool when negative values destroy orderly sum movement.
• Prefix sums turn "sum of a subarray" into "difference between two running totals".
• The map stores counts because the same running total can matter more than once.

This problem is a very good reminder that not every array question wants two pointers. Sometimes the better move is to stop steering a window and start counting earlier states instead.