Prefix sum + hash map

1
2
3
4
5
6
7
8
9
10
11
12

Let prefixSum[i] = sum of elements from 0 to i.
The sum of subarray from index (j + 1) to i is:
    subarraySum(j+1, i) = prefixSum[i] - prefixSum[j]

We want:
    prefixSum[i] - prefixSum[j] == k
Rearranging:
    prefixSum[j] == prefixSum[i] - k

Insight:
At each index i, we check if the HashMap has previously seen (prefixSum[i] - k)!
If it has, that earlier index j marks the start of a valid subarray summing to k!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCounts = new HashMap<>();
    prefixCounts.put(0, 1); // Base case: prefix sum of 0 occurred once before array starts

    int runningSum = 0;
    int count = 0;

    for (int num : nums) {
        runningSum += num;
        // Check if there is an earlier prefix sum that leaves a remainder of k
        if (prefixCounts.containsKey(runningSum - k)) {
            count += prefixCounts.get(runningSum - k);
        }
        prefixCounts.put(runningSum, prefixCounts.getOrDefault(runningSum, 0) + 1);
    }
    return count;
}