Subarray Sum Equals K
Medium Prefix sum + HashMap
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count the contiguous subarrays whose elements add up to exactly k. Values can be negative.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: count contiguous pieces that add to exactly k (negatives allowed).
Why this works: a piece from i+1 to j sums to k when prefix[j] - prefix[i] = k. So at each j, count earlier prefixes equal to prefix[j] - k, using a HashMap.
Example: nums = [1, 1, 1], k = 2
map {0:1}sum 1: need -1 → 0; map {0:1, 1:1}sum 2: need 0 → +1; map {…, 2:1}sum 3: need 1 → +1answer 2
✦Hints open one at a time
↗Approach
Scan once with a running sum. Before storing the current sum, add map[sum - k] to the answer. The initial {0: 1} counts subarrays that start at index 0. Sliding window doesn't work here because negatives break the "shrink when too big" rule.
</>Solution (Java)
import java.util.*;
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
count.put(0, 1); // empty prefix
int sum = 0, ans = 0;
for (int x : nums) {
sum += x;
ans += count.getOrDefault(sum - k, 0);
count.merge(sum, 1, Integer::sum);
}
return ans;
}
}!Common mistake
Forgetting the {0: 1} entry, which misses every subarray starting at index 0.
- Time: O(n).
- Space: O(n).
