Subarray Sum Equals K

Subarray Sum Equals K is a prefix-sum counting problem. Instead of checking every subarray, keep counts of prefix sums already seen and ask: "How many earlier prefixes would make the current subarray sum equal to k?"

Problem

Given an integer array nums and an integer k, return the total number of continuous subarrays whose sum equals k.

The array can contain positive numbers, negative numbers, and zeroes. That is why a sliding window is not reliable here.

Core Idea

Let prefix[i] be the sum from index 0 through index i.

For a subarray from j to i:

sum(j..i) = prefix[i] - prefix[j - 1]

We want:

prefix[i] - prefix[j - 1] = k

Rearrange it:

prefix[j - 1] = prefix[i] - k

So at each index, after computing the current prefix sum, count how many earlier prefix sums equal currentPrefix - k.

First Attempt

public int subarraySum(int[] nums, int k) {
    int n = nums.length;

    Map<Integer, Integer> sum = new HashMap<>();
    sum.put(0, 1);
    int currSum = 0;
    int count = 0;

    for (int i = 0; i < n; i++) {
        currSum += nums[i];

        int check = currSum - k;

        if (sum.containsKey(check)) count += sum.get(check);

        sum.put(currSum, sum.getOrDefault(currSum, 0) + 1);
    }

    return count;
}

This is already the right algorithm. The key detail is sum.put(0, 1), which handles subarrays that start at index 0.

Example:

nums = [3]
k = 3

At index 0, currSum = 3, so check = 0. The initial prefix count says one empty prefix existed before the array started, so the answer becomes 1.

Clean Version

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

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0, 1);

        int currentPrefix = 0;
        int count = 0;

        for (int num : nums) {
            currentPrefix += num;

            int neededPrefix = currentPrefix - k;
            count += prefixCounts.getOrDefault(neededPrefix, 0);

            prefixCounts.put(
                currentPrefix,
                prefixCounts.getOrDefault(currentPrefix, 0) + 1
            );
        }

        return count;
    }
}

This version keeps the same logic but names the map by what it stores: counts of prefix sums.

Walkthrough

Input:

nums = [1, 1, 1]
k = 2

Initial state:

prefixCounts = {0=1}
currentPrefix = 0
count = 0

Steps:

The two matching subarrays are:

[1, 1] at indices 0..1
[1, 1] at indices 1..2

Why Counts Matter

The map stores counts, not just whether a prefix sum exists.

Example:

nums = [0, 0]
k = 0

Every zero-length difference between prefix sums creates a valid subarray:

[0] at index 0
[0] at index 1
[0, 0] at indices 0..1

The answer is 3. A set would lose the duplicate prefix sums and undercount.

Complexity

Takeaways

• Prefix sums turn subarray-sum questions into difference questions.
• At each index, look for currentPrefix - k among earlier prefix sums.
• Store counts because the same prefix sum can appear multiple times.
• Initialize the map with 0 -> 1 to count subarrays starting at index 0.