LeetCode 560 Subarray Sum Equals K - Implementation

Here's the full solution:

function subarraySum(nums, k)
    count := 0
    runningSum := 0
    map := new HashMap()
    map[0] := 1
    // empty prefix exists once
    Each num in nums
        runningSum := runningSum + num
        // How many prefixes have sum = runningSum - k?
        count := count + map.getOrDefault(runningSum - k, 0)
        // Record this prefix sum
        map[runningSum] := map.getOrDefault(runningSum, 0) + 1
    return count

Time: $O(n)$. Space: $O(n)$ for the hash map.

The key insight: if prefix[j] - prefix[i] = k, then prefix[i] = prefix[j] - k. For each position j, you count how many earlier positions i satisfy this. The hash map stores prefix sum frequencies for $O(1)$ lookup.