Subarray Sum Equals K

Given an integer array and a target k, return the number of contiguous subarrays whose elements sum to k. The array can hold negatives and zeros. (LC 560)

It is Two Sum wearing a different coat. Two Sum asks "have I seen the number that completes this pair". This asks "have I seen the running total that completes this range", and how many times.

The recipe

Say before you type: "A subarray's sum is the difference of two prefix sums. So at each position, I want to know how many earlier prefix sums equal my current prefix minus k. I keep a map of prefix sums to how many times each has occurred."

1. Keep a running prefix sum, and a map of prefix → count.
2. Seed the map with {0: 1}: the empty prefix, so a subarray that starts at index 0 can be found.
3. For each number: add it to prefix.
4. Look up prefix - k in the map and add its count to the answer.
5. Then record the current prefix in the map.

The code

function subarraySum(nums: number[], k: number): number {
  const seen = new Map<number, number>([[0, 1]]); // the empty prefix
  let prefix = 0, count = 0;

  for (const n of nums) {
    prefix += n;
    count += seen.get(prefix - k) ?? 0;          // look BEFORE recording
    seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
  }

  return count;
}

Why this shape

If prefix[j] - prefix[i] = k, then the elements between i and j sum to k. For each j, every earlier i whose prefix equals prefix[j] - k is a different subarray ending at j, which is why the map has to hold counts, not just presence.

The tempting approach is a sliding window, and it works for arrays of positive numbers only. A negative number means growing the window can lower the sum, so there is no rule for when to shrink it. The prefix-sum map does not care about signs.

Complexity

	Cost	Because
Time	O(n)	One pass, with O(1) map operations
Space	O(n)	In the worst case every prefix sum is different

Traps

• Seeding the map with {0: 1}. Without it, any subarray that starts at the very beginning is missed. [1,2,3] with k = 3 should find both [1,2] and [3], and you lose the first.
• Look up, then record. Record the current prefix first and k = 0 counts every position as matching itself.
• Counts, not presence. [0, 0, 0] with k = 0 has six subarrays. A Set finds three.
• Sliding window. It fails the moment a negative number appears. [1, -1, 0] with k = 0 has three matches.
• Checking every pair. The brute force is a clean O(n²) and a perfectly good first answer. Say it, then ask whether the array could be large, and move to the map.

The pattern this trains

Prefix sums turn a range question into a two-point question, and a hash map answers two-point questions in O(1). It carries over to Continuous Subarray Sum (523, prefix sums modulo k), Subarray Sums Divisible by K (974) and Contiguous Array (525, turn the zeros into -1 and look for sum 0). The trigger is "how many subarrays" or "longest subarray" with a sum or balance condition, especially when the numbers can be negative.