Subarray Sum Equals K: Prefix Sums and a Hash Map in One Pass

"Count the contiguous subarrays that sum to k" looks like a sliding-window problem, and with only positive numbers it almost is. Add one negative number and the window breaks. The approach that always works is two ideas you already know glued together: prefix sums and the complement lookup from two sum. This article shows why the glue holds, where the famous 0: 1 comes from, and how to check it against a brute force.

The problem it solves

Given an array of integers, which may be negative, and a target k, count the pairs of positions i ≤ j such that nums[i] + … + nums[j] == k. For [1, 2, 3, -2, 2] with k = 3 there are four: [1, 2], [3], [2, 3, -2] and [3, -2, 2]. The last two overlap and both contain the negative number, which is where intuition about "windows" starts to slip.

Checking every start and end with a running sum is O(n²). The hash-map version is O(n).

The intuition

Write P[j] for the sum of the first j elements, so P[0] = 0. The sum of the subarray from index i to index j - 1 is P[j] - P[i]. Asking for that to equal k is asking for

P[i] == P[j] - k

So stand at position j with the running total P[j] and ask one question: how many earlier prefixes had the value P[j] - k? Each one is the start of a subarray that ends here and sums to k. That is two sum's "have I seen the complement?", moved from values onto running totals, and counting instead of stopping at the first hit.

A hash map from prefix value to how many times it has occurred answers the question in O(1). The order of the two map operations matters: look up first, then record the current total, so a subarray never pairs a prefix with itself.

The map starts as 0: 1 because the empty prefix is a real prefix. Without it, a subarray that starts at index 0 has no earlier prefix to match: on [3] with k = 3 the running total is 3, the lookup asks for 0, and only the seeded entry answers.

Why not a sliding window? A window relies on the sum growing when you extend and shrinking when you trim. With negative values, trimming can raise the sum, so neither end can be moved safely.

Watch it run

The animation uses [3, 4, -7, 1, 2] with target 3 and starts with the empty total 0 already in the map. Running total 3: look up 0, seen once, so one stretch ends here, [3]. Running total 7: 4 has never been a total, so record 7 and move on. Running total 0 after the -7: look up -3, never seen; the map now holds 0 twice. Running total 1: -2 never seen. Running total 3 again: look up 0, seen twice, so two stretches end here, [1, 2] and the whole array. Three stretches in one pass, and the negative value never mattered, which is exactly where a sliding window gives up.

The code

The lesson's function, plus a version that returns the subarrays themselves by storing positions instead of counts:

from collections import defaultdict

def count_subarrays(nums, k):
    seen = {0: 1}                              # the empty prefix counts once
    total = running = 0
    for x in nums:
        running += x
        total += seen.get(running - k, 0)      # earlier prefixes that close a k-sum
        seen[running] = seen.get(running, 0) + 1
    return total

def list_subarrays(nums, k):
    where = defaultdict(list)
    where[0].append(0)                         # prefix value -> positions where it occurred
    running, found = 0, []
    for j, x in enumerate(nums, start=1):
        running += x
        for i in where[running - k]:
            found.append(nums[i:j])
        where[running].append(j)
    return found

print(count_subarrays([1, 2, 3, -2, 2], 3))    # 4
print(list_subarrays([1, 2, 3, -2, 2], 3))     # [[1, 2], [3], [2, 3, -2], [3, -2, 2]]
print(count_subarrays([3, 4, -7, 1, 2], 3))    # 3
print(count_subarrays([0, 0, 0], 0))           # 6

The sliding window that works for positive numbers, and fails once a negative value appears:

def window_count(nums, k):
    left = window = total = 0
    for right, x in enumerate(nums):
        window += x
        while window > k and left <= right:
            window -= nums[left]               # assumes trimming always lowers the sum
            left += 1
        total += window == k
    return total

print(window_count([1, 2, 1, 2, 1], 3), count_subarrays([1, 2, 1, 2, 1], 3))   # 4 4
print(window_count([3, 4, -7, 1, 2], 3), count_subarrays([3, 4, -7, 1, 2], 3)) # 1 3

Both map versions against a brute force over every start and end, on 2,000 random arrays with negative values and zeros:

import random

def brute(nums, k):
    return sum(sum(nums[i:j]) == k
               for i in range(len(nums)) for j in range(i + 1, len(nums) + 1))

random.seed(17)
ok = True
for _ in range(2000):
    nums = [random.randint(-4, 4) for _ in range(random.randint(0, 12))]
    k = random.randint(-5, 5)
    listed = list_subarrays(nums, k)
    ok &= count_subarrays(nums, k) == brute(nums, k) == len(listed)
    ok &= all(sum(s) == k for s in listed)
print(ok)                                      # True

The complexity

• Brute force with a running sum per start: O(n²) time, O(1) space.
• Prefix map: O(n) time on average, one lookup and one insert per element, and O(n) space, since every prefix value may be distinct.
• Listing the subarrays is output-sensitive: there can be O(n²) of them, as [0, 0, 0] with k = 0 shows with six.

Where it goes wrong

• Forgetting 0: 1. Every subarray that starts at index 0 is missed.
• Recording before looking up. With k = 0 each position would match its own prefix and count an empty subarray.
• Storing a boolean or the last index instead of a count. Repeated prefix values, common with zeros and negatives, each start a different subarray.
• Reaching for a sliding window. It is correct only when every value is positive.
• Confusing count with longest. For the longest subarray summing to k, store the first index of each prefix value instead of a count.

When it shows up in interviews

It is a very common medium, and a favourite because the sliding-window reflex is wrong. Interviewers watch for the moment you notice negative numbers. The family is large: subarrays divisible by k (key the map by the prefix modulo k), contiguous arrays with equal zeros and ones (map zeros to -1, look for k = 0), the longest subarray with sum k, and path sum III on a binary tree, which runs the same map along a root-to-leaf path.

How to say it in an interview

"A subarray sum is a difference of two prefix sums, so the subarray ending here sums to k exactly when an earlier prefix equals the running total minus k. I keep a hash map from prefix value to how many times I have seen it, seeded with 0 once for the empty prefix. At each element I add the count for running - k, then record running. It is one pass, O(n) time and O(n) space, and unlike a sliding window it does not care about negative numbers."

The prefix idea itself is in prefix sums explained, and the lookup it borrows is in two sum with a hash map.