Subarray Sum Equals K

MediumPrefix Sum · Hash Map🧩 Prefix Sum LeetCode #560 ↗Updated Oct 30, 2026

Problem

Given an integer array nums (values may be negative) and an integer k, count how many contiguous, non-empty subarrays add up to exactly k.

Input[1,1,1], k=2Output2

Input[1,2,3], k=3Output2

1 ≤ n ≤ 2·10⁴ · -1000 ≤ nums[i] ≤ 1000 · -10⁷ ≤ k ≤ 10⁷

Try it yourself

Java

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

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A subarray (j..i] sums to k exactly when prefix[i] - prefix[j] = k, i.e. prefix[j] = prefix[i] - k. So while scanning, just ask: how many earlier prefixes equal sum - k?

PatternPrefix Sum

Instinct Repeated range-sum queries, or "count subarrays whose sum equals / divides K" with negatives allowed? Store running totals and subtract two of them.

Memory hack Any range is two prefixes apart - sum(i..j) = P[j+1] - P[i], so remember every P you've passed.

Open the Prefix Sum guide →

Approaches

Brute ForceEnumerate & Re-sum Every Subarray

Time O(n³)Space O(1)

Try every pair (start, end) and add up nums[start..end] from scratch with a third loop. Count the pairs whose sum equals k.

Java

public int subarraySum(int[] nums, int k) {
    int count = 0;
    for (int start = 0; start < nums.length; start++) {
        for (int end = start; end < nums.length; end++) {
            int sum = 0;
            for (int m = start; m <= end; m++) sum += nums[m];
            if (sum == k) count++;
        }
    }
    return count;
}

Obviously correct, but cubic — far too slow for n = 2·10⁴.

BetterRunning Sum per Start

Time O(n²)Space O(1)

The sum of [start..end] is the sum of [start..end-1] plus nums[end]. Extending the end pointer and keeping a running total removes the innermost loop.

Java

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

Quadratic, constant memory — ~2·10⁸ steps at the limit.

OptimalPrefix Sum + Hash Map of Counts

Time O(n)Space O(n)

Keep a running prefix sum and a map prefix value → how many times seen. Every earlier prefix equal to sum - k starts a subarray ending here with sum k. Seed the map with {0: 1} so subarrays starting at index 0 count. Negatives rule out a sliding window — sums are not monotonic.

Java

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

Dry run[1,2,3], k=3

i current changed

i=0
1
i
2

3

sum=1, need -2: 0
i=1
1

2
i
3

sum=3, need 0: +1 → 1
i=2
1

2

3
i
sum=6, need 3: +1 → 2 ✔

One pass with O(1) average map operations.

Pro tip

Query the map before inserting the current prefix, otherwise k = 0 would count an empty subarray.

At a glance

Level	Approach	Time	Space
Brute Force	Enumerate & Re-sum Every Subarray	`O(n³)`	`O(1)`
Better	Running Sum per Start	`O(n²)`	`O(1)`
Optimal	Prefix Sum + Hash Map of Counts	`O(n)`	`O(n)`

Common pitfalls

Forgetting seen.put(0, 1) — misses subarrays that start at index 0.
Using a sliding window — fails with negative numbers.
Storing a boolean/index instead of a count — repeated prefixes each add a subarray.

Interview tips

Ask early whether values can be negative; it decides window vs. prefix map.
Write the identity prefix[i] - prefix[j] = k before coding.
Same template solves divisible-by-K and binary-subarray variants.

Pattern

Prefix sum + hash map → count/locate subarrays with a target sum when values can be negative.

My notes saved in this browser