#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/prefix-sums/subarray-sum-equals-k-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/prefix-sums/subarray-sum-equals-k-implementation

Repovive

LeetCode 560 Subarray Sum Equals K - Implementation - Prefix Sums | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 560 Subarray Sum Equals K - Implementation

The code

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.