You're given an integer array nums and an integer k. Count how many subarrays of nums sum to exactly k, and return that count.
A subarray is a contiguous, non-empty block of the array — pick a start index and an end index and take everything between them, in order. Picking scattered elements doesn't count.
Note that nums may contain negative numbers and zeros, and valid subarrays may overlap — every distinct (start, end) pair whose sum is k counts once.
nums[i..j] is runningTotal(j) - runningTotal(i-1) — a subarray sum is a difference of two prefix sums. What are you really searching for at each position?prefix - k? A hash map from prefix sum → frequency answers that in O(1). Seed it with 0 → 1.nums, extending the window can decrease the sum, so the pointer-movement logic breaks. Sliding window works for the all-positive variant only.0 exists before the array starts — the empty prefix. Without seeding seen[0] = 1, any subarray that starts at index 0 and sums to k would never be counted.seen[prefix - k] first, then record the current prefix. If you record first and k = 0, the current prefix matches itself and you incorrectly count an empty subarray at every step.O(n) time and O(1) space — a strictly better trade-off the moment the negatives guarantee appears.i - firstIndex[prefix - k] — that's the Longest Subarray with Sum K problem.O(rows^2 * cols) — the 1-D trick is the inner engine.0 → 1 seed is the same idea as a sentinel node in a linked list: invent an imaginary 'empty prefix' so the boundary case stops being special.Input: nums = [1,1,1], k = 2 Output: 2 Two subarrays sum to 2: [1,1] starting at index 0, and [1,1] starting at index 1.
Input: nums = [1,2,3], k = 3 Output: 2 [1,2] and [3] both sum to 3.
Input: nums = [1,-1,0], k = 0 Output: 3 [1,-1], [0], and [1,-1,0] all sum to 0 — negatives and zeros make extra answers possible.
- 1 <= nums.length <= 2 * 10^4 - -1000 <= nums[i] <= 1000 - -10^7 <= k <= 10^7
Count the subarrays that sum to k — and because nums can hold negatives and zeros, the usual sliding window is off the table. This problem is the classic gateway to one of the most reused interview tricks there is: prefix sums + a hash map. Here's how to get there from scratch.
prefix[j] = nums[0] + … + nums[j] — any subarray sum is a difference of two of these.O(1) insert and lookup — here the map records how many times each prefix sum has appeared.n^2 pair checks at n = 2 * 10^4 is about 2 * 10^8 operations — too slow — while one pass is instant.In plain English: count every contiguous, non-empty run of elements whose values add up to k.
Formally: given nums of length n and an integer k, return the number of index pairs (i, j) with 0 <= i <= j < n such that nums[i] + nums[i+1] + … + nums[j] = k.
Worked example — nums = [1, 2, 3], k = 3
elements: 1 2 3
prefix sums: 0 1 3 6
^ ^ ^
pairs of prefixes that differ by 3:
3 - 0 = 3 → subarray [1, 2]
6 - 3 = 3 → subarray [3]
answer: 2
Asking two or three sharp questions before coding shows an interviewer you design for the real input, not the happy path.
“Can nums contain negative numbers or zeros?”
Yes — and this is the whole game. With negatives, growing a window can shrink its sum, so a sliding window's move-the-pointers logic breaks. The hash-map approach doesn't care about sign.
“Can k be zero or negative?”
Yes. k = 0 is especially tricky — runs like [1, -1] and lone zeros both count, and it exposes a classic bug in the map-update order.
“Do overlapping subarrays count separately?”
Yes — every distinct start-end pair counts once, even if two subarrays share elements or have identical values.
“Do we return the count or the subarrays themselves?”
Just the count — which is why we can get away with never materialising a single subarray.
“How large can the array be?”
Up to 2 * 10^4 elements. An O(n^2) scan is roughly 2 * 10^8 sum checks — over budget. The constraint is telling you to find O(n).
Before I code, a few quick questions.
Can the array contain negatives and zeros? If so, a sliding window won't work and I'll reach for prefix sums.
Can k itself be zero or negative?
And overlapping subarrays each count separately, correct? Then I'll count index pairs, not distinct value-sequences.
Let prefix[j] be the sum of the first j elements. Then the sum of nums[i..j] is prefix[j+1] - prefix[i] — the odometer trick. Every subarray question about sums is secretly a question about pairs of prefix sums.
nums = [ a0 a1 a2 a3 ] prefix = p0 p1 p2 p3 p4 (p0 = 0) sum(a1..a3) = p4 - p1
We need pairs where prefix[j] - prefix[i] = k, i.e. prefix[i] = prefix[j] - k. Walk left to right; at each position, the number of valid subarrays ending here is exactly how many earlier prefixes equal prefix - k. A hash map from prefix sum → frequency answers that in O(1), turning an O(n^2) pair hunt into a single pass.
Before any element, the running total is 0 — so the map starts as {0: 1}; without it, every subarray that starts at index 0 goes uncounted. And because negatives and zeros let the same prefix sum appear many times, the map must store counts, not a single index — each occurrence starts a distinct valid subarray.
| Brute force | Optimal | |
|---|---|---|
| Idea | Run a running sum from every start index | One pass with prefix sums + hash map |
| Time | O(n^2) | O(n) |
| Space | O(1) | O(n) |
| At n = 2 * 10^4 | ~2 * 10^8 checks — TLE | 2 * 10^4 steps — instant |
Full, runnable code for both lives in the Approaches selector below.
Key takeaway
When a problem asks about subarray sums with negatives allowed, think prefix sums: a subarray sum is a difference of two running totals, so a hash map of prefix → frequency (seeded with the empty prefix) counts all matches in one pass.
seen = {0: 1} # the empty prefix
prefix = 0, count = 0
for x in nums:
prefix += x
count += seen[prefix - k] # subarrays ending here
seen[prefix] += 1 # record AFTER the lookup
return count