Subarray Sum Equals K
On this page
Problem statement
Given an array of integers and a number k, count how many contiguous subarrays add up to exactly k. The array can contain negative numbers and zeros. Subarrays at different positions count separately, even if they hold the same values.
It's the cleanest test of the prefix-sum idea: turn "sum of a range" into "difference of two running totals", then count matching pairs with a hash map, as in Two Sum. Original problem: LeetCode 560.
Example
![Five different contiguous runs of [1, 2, 3, −2, 2, 0] add up to 3; zeros and negatives let runs overlap and extend.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-a424742c.png)
Input: nums = [1, 2, 3, -2, 2, 0], k = 3
Output: 5 # [1,2], [2,3,-2], [3], [3,-2,2], [3,-2,2,0]
Input: nums = [1, 1, 1], k = 2
Output: 2 # [1,1] at positions 0–1 and 1–2
Constraints (assumed)
- 1 ≤ n ≤ 2 × 10⁴.
- −1,000 ≤ nums[i] ≤ 1,000; −10⁷ ≤ k ≤ 10⁷.
What this question tests
- Turning a range sum into a difference of prefix sums.
- Noticing that negatives break the sliding window, and explaining why.
- Reusing the Two Sum lookup with counts instead of indices, including the empty-prefix seed.
Questions to ask first
- Can values be negative or zero? (Here: yes. With only positives, a sliding window works in O(1) space.)
- Count, or return the subarrays? (Here: the count. Listing them can be O(n²) in output size.)
- Contiguous only? (Yes; otherwise it's a subset-sum problem, which is much harder.)
- Can the count overflow? With n = 2 × 10⁴ the count is at most about 2 × 10⁸, so 32-bit is fine; for larger n use 64-bit.
Try it first
Before reading on, try it yourself: write the sum of nums[i..j] using running totals. What value would you need to have seen earlier for the subarray ending at j to sum to k? Sketch the idea and its complexity, then open the solution.
Approach ladder
Weaktry every subarray
For every start i, extend the end j and keep a running sum; count when it equals k. O(n²) time, O(1) space. Recomputing each sum from scratch makes it O(n³), so at least keep the running sum.
Good(but wrong here): sliding window
Grow the window to the right and shrink from the left when the sum is too big. It's O(n) and correct when all numbers are positive, because adding always increases the sum. With negatives or zeros, shrinking can be wrong in both directions, so it misses answers. Mention it to show you know why it fails.
Strongprefix sums + hash map of counts
sum(i..j) = prefix[j] − prefix[i − 1]. For each j, count earlier prefixes equal to prefix[j] − k using a hash map. One pass, O(n) time and O(n) space, and negatives are no problem.
Solution
Step 1: a range sum is a difference of prefix sums

Let prefix be the sum of everything so far. A subarray that ends at the current position and starts right after some earlier position i has sum prefix − prefix_i. Setting that equal to k gives prefix_i = prefix − k. So the number of good subarrays ending here is the number of earlier prefixes equal to prefix − k.
Step 2: count earlier prefixes in a hash map
Seed the map with {0: 1}: before reading anything, the running total is 0, and that "empty prefix" is what makes subarrays starting at index 0 count.
from collections import defaultdict
def subarray_sum(nums, k):
counts = defaultdict(int)
counts[0] = 1 # the empty prefix
prefix = answer = 0
for x in nums:
prefix += x
answer += counts[prefix - k]
counts[prefix] += 1
return answer
int subarraySum(int[] nums, int k) {
Map<Integer, Integer> counts = new HashMap<>();
counts.put(0, 1); // the empty prefix
int prefix = 0, answer = 0;
for (int x : nums) {
prefix += x;
answer += counts.getOrDefault(prefix - k, 0);
counts.merge(prefix, 1, Integer::sum);
}
return answer;
}
int subarraySum(const vector<int>& nums, int k) {
unordered_map<int, int> counts{{0, 1}}; // the empty prefix
int prefix = 0, answer = 0;
for (int x : nums) {
prefix += x;
auto it = counts.find(prefix - k);
if (it != counts.end()) answer += it->second;
counts[prefix]++;
}
return answer;
}
func subarraySum(nums []int, k int) int {
counts := map[int]int{0: 1} // the empty prefix
prefix, answer := 0, 0
for _, x := range nums {
prefix += x
answer += counts[prefix-k]
counts[prefix]++
}
return answer
}
Time: O(n). Space: O(n) for the map.
Tracing [1, 2, 3, −2, 2, 0], k = 3: prefixes are 1, 3, 6, 4, 6, 6. At 3 we find one earlier 0 (+1); at the first 6 one earlier 3 (+1); at 4 one earlier 1 (+1); at the second 6 one earlier 3 (+1); at the third 6 still one earlier 3 (+1). Total 5. The order matters: look up first, then record, so a prefix never matches itself (which would count an empty subarray when k = 0).
The common bug
![Without the {0: 1} seed, a subarray that starts at index 0 has no earlier prefix to match, so [3] with k = 3 returns 0 instead of 1.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/002-d8fbf266.png)
Forgetting counts[0] = 1 silently drops every subarray that starts at the beginning of the array. It passes many random tests and fails on the simplest one: [3] with k = 3. The second classic mistake is reaching for a sliding window because "subarray" sounds like one; it breaks as soon as a negative number appears.
Edge cases
- Single element equal to k:
[3], k = 3 → 1 (needs the seed). - k = 0 with zeros:
[0, 0], k = 0 → 3 ([0],[0],[0, 0]). - All negatives: works the same; prefixes just decrease.
- No match: returns 0.
- Large inputs: prefix sums can exceed 32 bits if values or n are large; use 64-bit integers.
Variants seen in interviews
- Only positive numbers: sliding window, O(1) space.
- Longest subarray with sum k: store the first index of each prefix instead of a count; length is
j − first[prefix − k]. - Subarray sum divisible by k: key the map by
prefix mod k(normalize negatives). - Continuous subarray sum (a multiple of k, length at least 2): store first indices of
prefix mod k. - Equal number of 0s and 1s: map 0 → −1 and look for a subarray summing to 0.
- 2D version (submatrices summing to k): fix two rows, compress columns, run this 1D algorithm. O(rows² · cols).
Follow-up questions
- Why does the sliding window fail with negative numbers? Give a small counterexample.
- How would you return the longest such subarray instead of the count?
- How would you list all of them, and what is the worst-case output size?
- The numbers arrive as a stream. Can you report the running count after each one?
- How does the code change if you need sums divisible by k?
- Extend it to a 2D matrix: count submatrices that sum to k.
Related
- Patterns: Hash Maps and Prefix Sums, Sliding Window (the positive-only variant)
- Similar problems: Two Sum, Product of Array Except Self, Max Consecutive Ones III, Maximum Subarray
- Data structures: Hash Maps, Arrays and Strings