Problem 5.4 · Prefix SumMedium

Subarray Sum Equals K

PatternPrefix Sum + Hash Map Hash Map Lookup (Complement)

What it teaches: Count subarrays with sum k, even with negative numbers, by counting earlier prefix sums equal to sum − k.

Practise it on judges as “Subarray Sum Equals K”.

The problem

Given an integer array nums and an integer k, return the number of contiguous, non-empty subarrays whose sum equals k.

Example 1

Input: nums = [1, 1, 1], k = 2
Output: 2

Example 2

Input: nums = [1, 2, 3], k = 3
Output: 2

[1, 2] and [3].

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
−1000 ≤ nums[i] ≤ 1000
−10⁷ ≤ k ≤ 10⁷

Pattern clues in the wording

→ Count subarrays with an exact sum
→ Negative numbers allowed, so a sliding window fails
→ Range sums → prefix sums

These clues point to Prefix Sum + Hash Map: Count subarrays with a target sum by remembering how often each running total has appeared.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int subarraySum(int[] nums, int k) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,1,1] k = 2	2
2	nums = [1,2,3] k = 3	2
3	nums = [1,-1,0] k = 0 [1, −1], [0] and [1, −1, 0]	3

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Brute force: every start, growing sum · O(n²)2. Optimal: prefix sums with a hash map · O(n)

Brute force: every start, growing sum

Time O(n²) Space O(1)

For each start, extend the end and count every time the running sum equals k.

Approach 1

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) count++;
            }
        }
        return count;
    }
}

Verdict: 2 × 10⁸ steps at the limit: too slow. The repeated work is recomputing sums that prefix sums already know.

Optimal: prefix sums with a hash map

Time O(n) Space O(n)

Keep a running sum and a map of how often each prefix sum has occurred (seeded with 0 → 1). At each element, add seen[sum − k] to the count, then record sum.

▶ Dry run: Counting with prefix sumsnums = [1, 1, 1], k = 2

seen(map)

0 → 1

State(vars)

sum = 0count = 0

Step 1/4Seed: prefix sum 0 has been seen once (the empty prefix).

Approach 2

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);
        int sum = 0, count = 0;
        for (int x : nums) {
            sum += x;
            count += seen.getOrDefault(sum - k, 0);
            seen.merge(sum, 1, Integer::sum);
        }
        return count;
    }
}

Verdict: One pass. The canonical answer.

Before you submit

Edge cases and common mistakes

Test these inputs

k = 0 with zeros in the array
Negative numbers
The whole array sums to k

Mistakes people make

Using a sliding window (fails with negatives).
Forgetting the {0: 1} seed.
Recording sum before counting, which counts an empty subarray when k = 0.

Interview

Follow-up questions

How would you return the longest subarray with sum k instead?

What about subarrays whose sum is divisible by k?

Command Palette