Subarray Sum Equals K
Problem Statement
Given an integer array nums and an integer k, return the total number of contiguous subarrays whose sum equals k.
Input
An integer array nums and an integer target sum k.
Output
An integer: the number of contiguous subarrays with sum exactly k.
Constraints
- •
1 <= nums.length <= 2 * 10^4 - •
-1000 <= nums[i] <= 1000 - •
-10^7 <= k <= 10^7
Examples
Example 1
nums = [1,1,1], k = 2
2Example 2
nums = [1,2,3], k = 3
2Example 3
nums = [1,-1,0], k = 0
3Learning Objectives
- Recognise target subarray sums as differences between two prefix sums.
- Use a frequency map because multiple earlier prefixes can create different valid subarrays.
- Seed prefix sum **0** to count subarrays that start at index **0**.
- Avoid sliding-window assumptions when negative numbers are allowed.
Intuition
Pattern Recognition
This is a prefix-sum-with-hashmap problem because it asks about sums of arbitrary contiguous subarrays, and nums can include negative values. A sliding window is not reliable with negatives because expanding can decrease the sum and shrinking can increase it. The direct O(n^2) approach tries every start and recomputes or extends every end.
A subarray ending at the current index has sum k exactly when some previous prefix sum equals currentPrefix - k. Instead of searching all previous prefixes, store how many times each prefix sum has appeared. When the needed prefix appears multiple times, each occurrence gives a different valid subarray ending here.
Common mistakes
- ×Using a sliding window even though negative numbers break the monotone-sum property.
- ×Storing only whether a prefix sum exists instead of its frequency, which undercounts duplicates.
- ×Forgetting **map.put(0, 1)** and missing subarrays that start at index **0**.
- ×Updating the map before counting, which can incorrectly count an empty subarray when **k = 0**.
Algorithm Explanation
Key idea
Let sum be the prefix sum through the current index. A previous prefix p creates a subarray of sum k if sum - p = k, so p = sum - k. Count how many previous prefixes equal sum - k, add that frequency to the answer, then record the current prefix for future indices.
Walkthrough
For nums = [1,2,3] and k = 3, start with map {0:1}. At index 0, sum = 1 and the needed prefix is -2, which is absent, so the answer stays 0 and map becomes {0:1, 1:1}. At index 1, sum = 3 and the needed prefix is 0, present once, so [1,2] is counted. At index 2, sum = 6 and the needed prefix is 3, present once, so [3] is counted. The final answer is 2.
Algorithm
- Create a hashmap from prefix sum to frequency.
- Seed the map with prefix sum 0 appearing once.
- Scan nums, maintaining the running prefix sum.
- For each value, add it to sum and compute needed = sum - k.
- Add the frequency of needed to the answer.
- Increment the frequency of the current sum in the map.
- Return the accumulated answer.
Solutions
Solution: Prefix-sum frequencies
Keep counts of all prefix sums seen before the current index. The number of subarrays ending at the current index is exactly the count of previous prefixes equal to sum - k.
Step-by-step
- Initialise prefixCount with 0 -> 1 for the empty prefix.
- Sweep left to right, adding each number to sum.
- Look up sum - k and add that frequency to answer.
- Record the current sum after counting so future subarrays can start after this index.
- Return answer after the scan.
O(n)
O(n)
Each index performs constant expected-time hashmap operations, and up to n distinct prefix sums may be stored.
Java implementation
Dry Run
Sample input
nums = [1,2,3], k = 3. The map starts as {0:1} to represent the empty prefix before index 0.
| index | nums[index] | prefix sum | needed prefix sum | map before update | answer |
|---|---|---|---|---|---|
| 0 | 1 | 1 | -2 | {0:1} | 0 |
| 1 | 2 | 3 | 0 | {0:1, 1:1} | 1 |
| 2 | 3 | 6 | 3 | {0:1, 1:1, 3:1} | 2 |
A needed prefix is found while processing index 1 and again while processing index 2, so two subarrays sum to 3.
Interview Tips
Lead with the equation currentPrefix - previousPrefix = k. That equation makes the hashmap feel necessary rather than magical. Be explicit that the map stores frequencies, not just membership, because duplicate prefix sums represent different start positions. Also say that the lookup happens before inserting the current prefix to avoid counting empty subarrays.
Likely follow-ups
- How would you return the actual start and end indices for one matching subarray?
- How would you count subarrays whose sum is divisible by **k**?
- How would the solution change if all numbers were positive and you only needed existence?
- What changes if the array is streamed and you need the running count after every new value?
Similar Problems
Key Takeaways
- A target subarray sum is a difference between two prefix sums.
- The required previous prefix at each index is **currentPrefix - k**.
- Prefix frequencies are necessary when multiple starts produce valid subarrays.
- Seed **0 -> 1** so subarrays beginning at index **0** are counted naturally.