Prefix Sums with a Hash Map

1.The key equation

The sum of a[i..j] is prefix[j + 1] − prefix[i]. It equals k exactly when prefix[i] = prefix[j + 1] − k. So while scanning, for the current running sum sum, the number of subarrays ending here with sum k is the number of earlier prefix sums equal to sum − k.

Store how many times each prefix sum has occurred in a map. Seed it with {0: 1} for the empty prefix, so subarrays starting at index 0 are counted.

2.The same idea in code

Five lines inside the loop: add the element to sum, count earlier prefix sums equal to sum − k, then record sum. Running it on the traced input prints 3. When you trace by hand, checking against real output like this catches arithmetic slips.

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

public class Main {
    static int subarraySum(int[] a, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);
        int sum = 0, count = 0;
        for (int x : a) {
            sum += x;
            count += seen.getOrDefault(sum - k, 0);
            seen.merge(sum, 1, Integer::sum);
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(subarraySum(new int[]{1, 2, 1, -1, 2}, 3));
    }
}

3

3.Why not a sliding window?

A sliding window works when growing the window always increases the sum (all positives). With negatives, shrinking the window can increase the sum, so the window rule breaks. Prefix sums with a hash map don't care about signs.