Problem statement
You have an integer array and a target k. Count the continuous, nonempty pieces of the array whose values add up to that target.
A continuous piece is called a subarray. You can choose its starting and ending positions, but you cannot skip a value in between. Different positions count as different subarrays, even when their values are identical.
We are solving LeetCode 560: Subarray Sum Equals K. The array has between 1 and 20,000 elements. Values may range from −1,000 to 1,000, and k may range from −10,000,000 to 10,000,000. Negative numbers and zeros are allowed.
The answer is a count, not the length of the longest range and not a list of the matching ranges.
Constraints & requirements
- INPUT
- 1 to 20,000 integers; negatives and zeros allowed
- RETURN
- Number of nonempty matching subarrays
- TARGET
- Expected O(n) time using prefix frequencies
Examples 5 test cases
Example 1 Repeated totals
- Input
[1, -1, 1], k = 1- Output
3
Two earlier zero-total boundaries create two matches at the final index.
Example 2 All zeros
- Input
[0, 0, 0], k = 0- Output
6
Requires frequencies and excludes empty ranges.
Example 3 Starts at zero
- Input
[2], k = 2- Output
1
Requires the initial empty-prefix boundary.
Example 4 Negative target
- Input
[-1, -1, 1], k = -1- Output
3
Confirms that negative targets and values are supported.
Example 5 No match
- Input
[1, 2], k = 9- Output
0
Checks the missing-answer result.
Hints Optional
01Subtract two totals
A range ending now has sum K when an earlier total equals current minus K.
02Store frequencies
Several earlier boundaries may have the same total. Each one gives a different starting position.
03Protect the ordering
Start with zero appearing once. Look up earlier matches before recording the current boundary.
How to think before coding
Start with the nested loops that check every start/end pair. The repeated work is searching earlier boundaries for each end. Rearrange currentPrefix−oldPrefix=k into oldPrefix=currentPrefix−k. Several old boundaries may share that total, so store a frequency and add all matches. Initialize 0→1 for the empty prefix, and query before inserting the current prefix to exclude empty ranges.
Start with a small example
Take [1, 1, 1] and k = 2.
Indexes: 0 1 2 Values: 1 1 1 Indexes 0..1 → [1, 1] → sum 2 ✓ Indexes 1..2 → [1, 1] → sum 2 ✓ Answer: 2
These two pieces look the same, but they use different positions. Both count.
For [1, 2, 3] with k = 3, the matches are [1, 2] and [3]. A subarray can contain just one value.
How do we recognize this pattern?
Look for three clues:
- We are counting continuous ranges.
- Each range must have an exact sum.
- Negative numbers are allowed, so a simple positive-only sliding window is unsafe.
That combination suggests prefix sums plus a frequency map. If prefix sums are new, first read Prefix Sum in Java. The rest of this article builds the solution without assuming you have memorized a formula.
Approach 1: Try every subarray
Pick a starting position. Move the ending position forward, adding one value at a time. Whenever the running sum equals k, increase the count.
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
long sum = 0; // Start a new running sum for this starting index.
for (int end = start; end < nums.length; end++) {
sum += nums[end]; // Extend the current range by exactly one value.
if (sum == k) {
count++; // This start/end pair forms one valid nonempty subarray.
}
}
}
return count;
}
}We reuse the sum as end moves forward. We do not add the whole range from scratch each time.
There are n × (n + 1) / 2 nonempty subarrays, so this takes O(n²) time and O(1) extra space. It is useful for understanding the problem and checking a faster solution on small arrays. For 20,000 values, it can examine 200,010,000 ranges.
Do not stop when sum becomes greater than k. With negative numbers, it can decrease later. In [3, -1] with k = 2, the first value is too large, but the whole range is a match.
Why not just use a prefix array?
A prefix array lets us calculate the sum of any chosen range in O(1) time. But if we still choose every possible start and end, we still have O(n²) ranges to check.
We need to avoid trying every start. Instead, ask which earlier running totals would make a valid subarray ending here.
Approach 2: Turn the range into two boundaries
Intuition behind the two boundaries
A prefix sum is a running total from the beginning. Suppose our total now is current, and an earlier total was earlier.
sum of the values between those boundaries = current - earlier
For that difference to equal k:
current - earlier = k earlier = current - k
At each position, we therefore ask:
InsightHow many earlier prefix totals equal current − k?
Each matching earlier boundary gives one valid starting position. A frequency map answers that question without scanning all earlier positions.
Why store frequencies?
Consider [0, 0, 0] with k = 0. Every running total is zero, but each occurrence represents a different boundary.
- At the first zero, there is 1 earlier zero-total boundary: add 1 answer.
- At the second zero, there are 2: add 2 answers.
- At the third zero, there are 3: add 3 answers.
The total is 1 + 2 + 3 = 6.
A set only remembers whether zero appeared. We need a map that remembers how many times it appeared.
Why do we start with 0 appearing once?
Before reading the array, we have processed no values, so our running sum is zero. That empty prefix is a real boundary before index 0.
It lets us count ranges starting at index 0. For [2] with k = 2, the current sum is 2, so we need an earlier sum of 2 - 2 = 0. The initial boundary supplies it.
The empty prefix is not an answer by itself. A valid answer contains at least one array element.
Optimal Java solution
This version uses LeetCode’s required method signature.
import java.util.HashMap;
import java.util.Map;
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Long, Integer> frequency = new HashMap<>();
frequency.put(0L, 1); // The empty prefix lets a subarray start at index zero.
long current = 0; // Use long for accumulated sums, even though each input is int.
int count = 0;
for (int value : nums) {
current += value; // Prefix sum through the current index.
long needed = current - k; // Removing this earlier total leaves sum k.
count += frequency.getOrDefault(needed, 0); // Each earlier match is a different start.
// Store only after lookup: the current boundary must not match itself.
frequency.put(current,
frequency.getOrDefault(current, 0) + 1);
}
return count; // Total number of valid start/end pairs.
}
}Count versus longest length
Do not copy the wrong map from another prefix sum question.
| Goal | Map stores | Why |
|---|---|---|
| Count subarrays with sum K | Frequency of each prefix total | Every earlier match adds one range |
| Longest subarray with sum K | Earliest index of each prefix total | Earliest start gives the longest range |
See Longest Subarray with Sum K to compare the two solutions side by side.
The idea to remember
Do not memorize only the Java code. Remember the question we ask at every step:
How many earlier totals can I subtract from this total to leave K?
The frequency map answers that question. Count those earlier boundaries first, then save the current boundary for the next step.
Step-by-step dry run

Read the text transcript
Use [1, -1, 1] with k = 1. It is small enough to follow and contains a repeated prefix total.
Before the loop:
current = 0
count = 0
frequency = {0: 1}| Index | Value | Current total | Needed: current − 1 | Earlier matches | Total count | Map after recording current |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 | 1 | {0: 1, 1: 1} |
| 1 | −1 | 0 | −1 | 0 | 1 | {0: 2, 1: 1} |
| 2 | 1 | 1 | 0 | 2 | 3 | {0: 2, 1: 2} |
At index 2, there are two earlier boundaries with total zero:
- Before the array: the range is indexes
0..2, or[1, -1, 1]. - After index
1: the range is index2..2, or[1].
Both end at index 2, but they start at different positions. Along with the first [1] at index 0, that makes three answers.
Understand the solution: ten questions answered
In the code, current is the current prefix sum, sometimes named prefixSum in other solutions. count is the answer so far. The map is called frequency because it stores how often each earlier total appeared.
1. Why do we keep adding elements to get the prefix sum?
We want a total from the beginning through the current index. When we move one position forward, the old total already contains all the earlier values. We only need to add the new value:
values: [1, -1, 1] running totals: 1 → 0 → 1
That is why we write current += value. We do not reset the total when we find a match: later ranges still need this history. Adding a negative value may decrease the total, which is perfectly valid.
2. Why do we calculate prefixSum − k?
Because it tells us exactly which earlier total we must remove to leave k:
current total − earlier total = k earlier total = current total − k
For example, if the current total is 10 and the target is 3, an earlier total of 7 would leave a range with sum 10 - 7 = 3.
current - k is the required earlier prefix, not the sum of the subarray and not an array index.
3. Why do we check whether prefixSum − k exists in the HashMap?
The map remembers totals at boundaries we have already passed. If the required total exists, there is at least one earlier boundary we can subtract to get a range ending here with sum k.
If it does not exist, there is no matching subarray ending at this index. We add zero and keep going; a later ending position may still produce a match.
The code combines the existence check and the count lookup:
count += frequency.getOrDefault(current - k, 0);This avoids searching every earlier position individually.
4. Why initialize the HashMap with 0 → 1?
Before reading any elements, there is one boundary with total zero: the boundary before index 0.
For [2] and k = 2, the current total becomes 2. We look for 2 - 2 = 0; that initial boundary lets us count [2].
Without (0, 1), ranges starting at index zero would be missed. It is not a fake subarray or a pre-counted answer. We still start the answer at zero.
In frequency.put(0L, 1), 0L is a long key because our prefix totals use long.
5. Why store the current prefix sum in the HashMap?
Today’s current boundary becomes an earlier boundary for future elements.
For [1, 2, 3] and k = 3, we record total 3 after processing index 1. At index 2, the total is 6, and we need 6 - 3 = 3. The stored boundary identifies the final [3] as a valid subarray.
Recording the total preserves information we will need later. We do it even if no subarray was found at the current step.
6. Why store frequency instead of only whether a total exists?
The same prefix total can appear at several different boundaries, especially when zeros or negative numbers are present. Those boundaries represent different possible starting positions.
For [1, -1, 1], total zero appears before the array and after index 1. A set would remember only “zero exists.” The frequency map remembers “zero appeared at two boundaries.”
We are counting all matching subarrays, so we must preserve that number. If we only wanted to know whether any match exists, a set could be enough.
7. If the required old prefix has frequency 2, why add 2?
Each matching earlier boundary creates one valid subarray ending at the current index. Two distinct boundaries therefore create two answers, not one.
At the final index of [1, -1, 1], with k = 1:
current = 1 needed = 1 - 1 = 0 frequency[0] = 2 Earlier boundary before index 0 → start at 0 → [1, -1, 1] Earlier boundary after index 1 → start at 2 → [1]
Both sum to 1. We add 2 to the answer already collected from previous ending positions.
8. Does frequency 2 mean two possible starts and two valid subarrays ending here?
Yes—when 2 is the frequency of the required total, current - k. Each earlier boundary gives a different starting point immediately after it. The ending point is the current index for both subarrays.
It does not mean two answers in the entire array, and it does not mean the current prefix itself is always a valid subarray. A map entry such as 0 → 2 means two occurrences of total zero, not “zero is at index two.”
9. Is “remove an old prefix of prefixSum − k” the correct understanding?
Yes. The current total covers everything from the beginning through this index. Subtracting an earlier prefix total removes the unwanted beginning and leaves the continuous part after that earlier boundary.
We maintain earlier prefix totals in a map, look for current - k, and add its frequency to the answer.
“Remove” means subtract the total mathematically. We do not remove array elements, delete the old map entry, or change the running total. The same old boundary may also help form a valid range ending later.
10. Why check the old prefix first, then store the current one?
We must compare the current boundary with strictly earlier boundaries so the range contains at least one element.
If we insert the current prefix first and k = 0, it can match itself. Subtracting a boundary from itself gives zero, but describes an empty range, which is not allowed.
For [0] and k = 0:
Correct order:
initial map {0: 1}
current becomes 0
look up 0 → add 1 valid range: [0]
record current → map becomes {0: 2}
Wrong order:
initial map {0: 1}
current becomes 0
record current → map becomes {0: 2}
look up 0 → incorrectly add 2, including an empty rangeKeep the order simple: add the value → count earlier matches → record the current total.
The final map update uses the old frequency plus one:
frequency.put(current, frequency.getOrDefault(current, 0) + 1);That is how we remember repeated boundaries without losing previous occurrences.
Why is the algorithm correct?
Before each element, the map stores the frequencies of all boundaries before it, including the initial empty prefix.
After adding this element, any valid range ending here must begin immediately after a boundary with total current - k. Conversely, every earlier boundary with that total gives a nonempty range ending here whose sum is k.
We add exactly that frequency. Then we record the new boundary, preserving the rule for the next element.
Every nonempty subarray has exactly one ending position. Counting it at that ending position means we neither miss it nor count it twice.
Time, space, and number types
The optimized approach takes expected O(n) time with a hash map and O(n) extra space in the worst case. Hash-map lookups are not a promise of worst-case constant time.
Under this problem’s constraints, even the largest count fits in Java’s int: at most 20,000 × 20,001 / 2 = 200,010,000. The prefix total also fits in int here, but using long makes the running-sum calculation safer if you later adapt the code to larger values.
For a generalized problem with larger arrays, use long for the count too. Check the constraints rather than assuming a number type is always sufficient.
Why the usual sliding window fails here
A common window rule is “if the sum is too large, remove values from the left.” That relies on nonnegative values: adding cannot decrease the sum, and removing cannot increase it.
Negative numbers break those rules. In [3, -1] with target 2, discarding 3 immediately loses the valid range [3, -1].
Zeros also complicate counting: multiple starting positions can give the same sum. A window that counts just one match per ending position can miss answers. Prefix frequencies handle positives, negatives, and zeros with the same logic.
Common mistakes
- Forgetting
(0, 1)and missing ranges starting at index zero. - Using a set and losing repeated-prefix frequencies.
- Inserting the current prefix before looking for earlier matches.
- Increasing the answer by one even when there are several matches.
- Resetting the running sum when it becomes negative; this is not Kadane’s algorithm.
- Sorting the array, which changes its continuous ranges.
- Counting an empty range when
k = 0.
Test cases worth checking
| Input | K | Expected | What it checks |
|---|---|---|---|
| [1, 1, 1] | 2 | 2 | Same values, different positions |
| [1, 2, 3] | 3 | 2 | A single value and a longer range |
| [1, −1, 1] | 1 | 3 | Repeated totals and negatives |
| [0, 0, 0] | 0 | 6 | Frequencies, not existence |
| [2] | 2 | 1 | Initial zero boundary |
| [3, −1] | 2 | 1 | Unsafe early window shrinking |
| [−1, −1, 1] | −1 | 3 | A negative target |
| [1, 2] | 9 | 0 | No valid range |
Try it yourself
Before running the solution, trace [2, -2, 2] with k = 2. Start with {0: 1} and write down the current total, needed total, and frequency after each value.
You should find three matches: the first [2], the final [2], and the whole [2, -2, 2].
Then compare your optimized answer against brute force on small arrays. That is a practical way to catch map-order and frequency bugs.
Practice next
Next lessonLongest Subarray with Sum KCompare a frequency map with an earliest-index map.