Subarray Sum Equals K Using Hash Map in DSA Python

Mental Model

We keep track of sums of numbers from the start to each position and use a map to find if a previous sum allows a subarray to sum to k.

Analogy: Imagine walking along a path and counting steps. If you know the total steps at two points, subtracting them tells you how many steps you took between those points. The map remembers these totals to quickly find matching distances.

Array: [1, 2, 3, 4]
Prefix sums: 0 -> 1 -> 3 -> 6 -> 10
HashMap stores sums seen so far with their counts:
{0:1, 1:1, 3:1, 6:1, 10:1}
Looking for subarray sum k=6 means checking if current_sum - k exists in map.

Dry Run Walkthrough

Input: array: [1, 2, 3], k=3

Goal: Find how many continuous subarrays sum exactly to 3

Step 1: Start with sum=0, map={0:1} to count empty prefix

sum=0, map={0:1}

Why: We count empty prefix to handle subarrays starting at index 0

Step 2: Add first element 1 to sum -> sum=1; check if sum-k=1-3=-2 in map (no)

sum=1, map={0:1, 1:1}

Why: No subarray ending here sums to k, add sum to map

Step 3: Add second element 2 -> sum=3; check sum-k=3-3=0 in map (yes, count=1)

sum=3, map={0:1, 1:1, 3:1}, count=1

Why: Found subarray [1,2] sums to k, increment count

Step 4: Add third element 3 -> sum=6; check sum-k=6-3=3 in map (yes, count=1)

sum=6, map={0:1, 1:1, 3:1, 6:1}, count=2

Why: Found subarray [3] sums to k, increment count

Result:

Final count=2; subarrays are [1,2] and [3]

Annotated Code

DSA Python

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        count = 0
        curr_sum = 0
        prefix_sums = {0: 1}  # sum 0 seen once
        for num in nums:
            curr_sum += num  # add current number to running sum
            if curr_sum - k in prefix_sums:
                count += prefix_sums[curr_sum - k]  # add count of prefix sums that match
            prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1  # record current sum
        return count

# Driver code
sol = Solution()
result = sol.subarraySum([1, 2, 3], 3)
print(result)

curr_sum += num # add current number to running sum

update running sum with current element

if curr_sum - k in prefix_sums:

check if a previous prefix sum allows subarray sum k

count += prefix_sums[curr_sum - k] # add count of prefix sums that match

increment count by number of matching prefix sums

prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1 # record current sum

record current prefix sum frequency

Output

2

Complexity Analysis

Time: O(n) because we traverse the array once and do constant time map operations

Space: O(n) because in worst case all prefix sums are unique and stored in the map

vs Alternative: Naive approach is O(n^2) by checking all subarrays; this method is much faster using prefix sums and a map

Edge Cases

empty array

returns 0 since no subarrays exist

DSA Python

for num in nums:

array with all zeros and k=0

counts all subarrays of zeros correctly using prefix sums

DSA Python

prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1

no subarray sums to k

returns 0 as count never increments

DSA Python

if curr_sum - k in prefix_sums:

When to Use This Pattern

When asked to find count of continuous subarrays with a target sum, use prefix sums with a hash map to track sums and find matches efficiently.

Common Mistakes

Mistake: Not initializing prefix_sums with {0:1}, missing subarrays starting at index 0
Fix: Initialize prefix_sums with {0:1} to count empty prefix sum

Mistake: Checking if curr_sum equals k instead of curr_sum - k in map
Fix: Check if curr_sum - k exists in prefix_sums to find valid subarrays

Summary

Counts how many continuous subarrays sum to a target k using prefix sums and a hash map.

Use when you need to find subarrays with a specific sum efficiently.

The key insight is that difference of prefix sums reveals subarray sums, and storing counts in a map lets you find matches fast.