Subarray Sum Equals K
Subarray Sum Equals K: count the contiguous subarrays whose elements sum to exactly k. The array may contain negative numbers.
- 1 <= nums.length <= 2 * 10⁴
- -1000 <= nums[i] <= 1000
- -10⁷ <= k <= 10⁷
Intuition
A subarray's sum is a difference of two prefix sums: 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. Counting how many earlier prefixes carry that value answers the whole question in one pass, and a hash map of prefix-sum frequencies provides those counts in constant time.
Contiguous-sum questions over an array that may contain negatives point to prefix sums with a hash map, not a sliding window. The presence of negative values is the deciding signal, because it removes the monotonicity a window relies on. Continuous Subarray Sum and Subarray Sums Divisible by K are the same idea modulo an extra step.
Approach
Before reading on: express the sum of a subarray as a difference of two prefix sums, then rearrange to see what you should be looking up. Work out why a set of seen prefixes is not enough, and what the map must be seeded with.
Turning a range sum into a difference
Let prefix[j] be the sum of the first j + 1 elements. Then any subarray i..j has sum prefix[j] − prefix[i−1]. Setting that equal to k and rearranging gives prefix[i−1] = prefix[j] − k. So while scanning, the number of subarrays ending at j with sum k equals the number of earlier prefix values equal to prefix[j] − k. This converts a search over O(n²) subarrays into a lookup per position.
Why frequencies, not a set
The same prefix sum can occur at several positions, and each occurrence begins a distinct valid subarray. A set records only whether a value appeared and would count one subarray where three exist. The map must therefore store how many times each prefix sum has been seen, and the counter is incremented by that frequency rather than by one. This is the difference between counting subarrays and detecting whether any exists.
The empty-prefix seed and why negatives break the alternatives
Seed the map with {0: 1}, representing the empty prefix before the array starts. Without it, any subarray beginning at index 0 goes uncounted, since its complement prefix[j] − k is 0 and that value would never have been recorded. Note also that negative numbers rule out the sliding-window approach entirely: a window's sum is no longer monotone as it grows, so shrinking it when the sum overshoots is invalid. Prefix sums do not depend on monotonicity, which is why they survive negatives. Time O(n), space O(n).
Solution & live demo
Common pitfalls
Omitting the {0: 1} seed
seen = defaultdict(int) prefix = 0
seen = defaultdict(int) seen[0] = 1
Any subarray starting at index 0 needs a prior prefix of 0 to be counted. Without the seed, [3] with k = 3 returns 0 instead of 1.
Storing prefixes in a set
if prefix - k in seen:
count += 1count += seen[prefix - k]
The same prefix sum can occur at multiple indices, each starting a distinct valid subarray. A set collapses them, undercounting whenever a prefix repeats.
Recording the current prefix before the lookup
seen[prefix] += 1 count += seen[prefix - k]
count += seen[prefix - k] seen[prefix] += 1
When k is 0 the current prefix would match itself, counting an empty subarray that does not exist. The lookup must see only prefixes from strictly earlier positions.
Edge cases
The {0: 1} seed is what makes it countable.
A prefix repeating itself counts, so zero-sum subarrays are found.
Prefix sums handle them; a sliding window would not.
No lookup ever hits and the count stays 0.
Each is counted separately, since each has its own starting prefix.