Count subarrays whose sum equals K

TL;DR: Sliding window fails on negatives, so use prefix sums: a subarray ending at j sums to k when some earlier prefix equals prefix[j] - k. Count earlier prefixes in a hashmap seeded with {0: 1}, one pass.

How to approach it First, set the trap aside out loud: "If all numbers were positive I'd use a sliding window, but negatives break window monotonicity, so I'll use prefix sums." Interviewers ask this specifically to see whether you know why sliding window fails. The core identity: sum(i..j) == prefix[j] - prefix[i-1], so a subarray ending at j sums to k exactly when some earlier prefix equals prefix[j] - k. Count earlier prefixes with a hashmap and you get one pass.

A strong answer

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    prefix = 0
    seen = defaultdict(int)
    seen[0] = 1                 # empty prefix: subarrays starting at index 0
    for x in nums:
        prefix += x
        count += seen[prefix - k]   # each earlier matching prefix = one subarray
        seen[prefix] += 1           # add AFTER counting, no zero-length subarrays
    return count

Two lines deserve narration. seen[0] = 1 is the empty prefix: without it, subarrays that start at index 0 are never counted (the most common bug on this problem). And incrementing seen[prefix] after the lookup prevents counting the empty subarray when k == 0. O(n) time, O(n) space.

Tests that target exactly those traps:

assert subarray_sum([1, 1, 1], 2) == 2
assert subarray_sum([1, 2, 3], 3) == 2          # [1,2] and [3]
assert subarray_sum([3, 4, 7, 2, -3, 1, 4, 2], 7) == 4   # negatives
assert subarray_sum([0, 0, 0], 0) == 6          # zeros: every i<=j pair
assert subarray_sum([], 5) == 0
assert subarray_sum([5], 5) == 1                # needs seen[0]=1

The [0,0,0], k=0 case is worth running by hand if the interviewer looks skeptical: it convinces both of you the counting logic is right.

The negatives case from the tests, traced by running the code, is the one to walk on a whiteboard because you can watch a negative number do the thing sliding window cannot handle:

Row two is the seed earning its keep: prefix 7 minus k is 0, and seen[0] = 1 is what counts the subarray [3, 4] that starts at index zero. Row six is the one that justifies the whole approach: the prefix dipped to 13 through the -3 and climbed back to 14, matching the earlier prefix of 7 and finding the subarray [7, 2, -3, 1], which sums to 7 through a negative number. A sliding window can never find that subarray, because on the way to it the sum overshoots to 16 and a window that shrinks on overshoot walks straight past the answer. The hashmap does not care that the prefix wandered; it only asks whether the right difference ever existed.

The last row is the trap. Sliding window is the instinct from every other subarray problem and it is wrong here, because a negative number means growing the window can decrease the sum, so shrinking on overshoot is no longer valid. Say that out loud and you have answered the follow-up before it arrives.

The other detail: seed the map with {0: 1}, or every subarray that starts at index 0 is missed.

What interviewers probe next (1) Return the subarrays, not the count? Store lists of indices per prefix value instead of counts; note the output itself can be O(n²), so the algorithm can't beat that. (2) All positive numbers, now what? Sliding window, O(1) space; explaining the monotonicity argument (window sum only grows as the right edge advances) closes the loop on the trap. (3) Longest subarray summing to k? Same hashmap but store the earliest index per prefix and never overwrite. (4) 2D version? Fix row pairs, reduce to 1D; sketch, don't implement. (5) FDE-flavored: "User activity deltas per minute; count windows where net change is zero", same code, and recognizing the mapping instantly is the point of asking warm-ups at all.

Common mistakes Reaching for sliding window and burning ten minutes before discovering negatives break it. Omitting seen[0] = 1. Incrementing the map before the lookup (overcounts when k == 0). Recomputing subarray sums in O(n²) and calling it done without flagging the cost: fine as a first version, but only if you say it's the brute force and improve it.