Know this before you start: “A hash map of totals seen so far, to count subarrays”
Counting subarrays with a map of totals
A adds up to k exactly when two running totals differ by k. Keep a count of every total seen so far and each step asks: how many earlier totals were total − k?
The idea
Any subarray nums[i..j] sums to prefix[j + 1] − prefix[i]. So “a subarray sums to k” means “an earlier total equals the current total minus k”.
Walk once with a running total. Before adding the current total to the map, look up how many times total − k has appeared: each one is the start of a subarray ending here.
Start the map with {0: 1}: the empty prefix, so subarrays that begin at index 0 are counted too. This works with negative numbers, where a doesn't.
Worked example
Subarrays summing to 0 in [1, −1, 1, −1]
- seen = {0: 1}. total 1: no earlier 1 → count 0; seen {0: 1, 1: 1}.
- total 0: one earlier 0 → count 1; seen {0: 2, 1: 1}. total 1: one earlier 1 → count 2.
- total 0: two earlier 0s → count 4. Those are [1, −1] twice, [−1, 1] and the whole array.
Pseudocode
The steps in plain words. ← means “set to”; indentation shows what's inside what.
See it run
The worked example, step by step, beside the Python. The highlighted line is the one running.
Step-by-step
nums = [1, -1, 1, -1], k = 0
nums
seen (total → times)
Solution · Pythonline 5
from collections import defaultdict def count_sum_k(nums, k):seen = defaultdict(int)seen[0] = 1 # the empty prefixtotal = count = 0for x in nums:total += xcount += seen[total - k] # earlier totals that leave exactly kseen[total] += 1return count print(count_sum_k([1, -1, 1, -1], 0)) # 4print(count_sum_k([1, 2, 3], 3)) # 2: [1, 2] and [3]Step 1 of 14· line 5
The empty prefix has total 0: count it once, so subarrays starting at index 0 are found too.
- just added
time and O(n) space for the map, instead of checking every subarray.
When you'll use it
- “How many subarrays sum to k”, “divisible by k” (store total % k), “equal 0s and 1s” (count 0 as −1).
- Any subarray question with negative numbers, where a sliding window can't decide when to shrink.
In the wild · Analytics dashboards: “Sales between March 3 and March 17” is one subtraction of two running totals, so charts answer any date range instantly instead of re-adding every day.
Common mistakes
- Forgetting seen[0] = 1, which misses every subarray that starts at index 0.
- Adding the current total to the map before looking up total − k: with k = 0 every position then counts itself.