Count the number of contiguous subarrays whose sum equals k.
Build prefix sums on the fly and store their frequencies in a hash map. For each new prefix sum P, a subarray ending at the current index has sum k if some earlier prefix sum equalled P - k. Look that up in the map in O(1). One pass, O(n) time and space.
How to think about it
The hidden test here is whether you reach for a sliding window and get burned. The moment the array can hold negatives or zeros, a window breaks — growing or shrinking it no longer moves the sum in a predictable direction, so you cannot decide which way to slide. The answer the interviewer wants is prefix sums backed by a hash map, which handles any integers and counts exact sums in one pass.
The idea rests on a small rearrangement. Let the running prefix sum at the current index be prefix. A subarray ending here sums to k exactly when some earlier prefix sum equalled prefix - k, because the elements between that earlier point and now are the difference. So you keep a map from each prefix sum to how many times it has appeared, and at every step you ask: how many earlier prefixes equalled prefix - k? That count is the number of qualifying subarrays ending at this index, and you add it to the total. Seed the map with {0: 1} — one empty prefix exists before the array starts — then walk once, looking up prefix - k and recording prefix as you go.
A worked example
from collections import defaultdict
def subarray_sum(nums, k):
count = defaultdict(int)
count[0] = 1 # one empty prefix exists before index 0
prefix = 0
result = 0
for num in nums:
prefix += num
result += count[prefix - k] # earlier prefixes that complete a sum of k
count[prefix] += 1
return result
print(subarray_sum([1, 1, 1], 2)) # [1,1] at 0-1 and at 1-2
print(subarray_sum([1, 2, 3], 3)) # [1,2] and [3]
print(subarray_sum([-1, -1, 1], 0)) # negatives, k=0
print(subarray_sum([3, 4, 7, 2, -3, 1], 7)) # mixed signs2
2
1
3Walk the first call, [1, 1, 1] with k=2. The prefixes are 1, 2, 3. At prefix 2 you look for 2 - 2 = 0, find it once (the seed), and count one subarray; at prefix 3 you look for 3 - 2 = 1, find it once, and count a second. Total 2 — the windows [1,1] at indices 0-1 and 1-2. The last call returns 3, not the larger number a quick eyeball might guess: with mixed signs the only sums of 7 are [3,4], the lone [7], and [7,2,-3,1], so trusting the prefix map over intuition is the point.