Subarray Sum Equals K - Prefix Sum Explained

Why it works

sum(i..j) = prefix[j] - prefix[i-1], so a subarray summing to k ends at j exactly when an earlier prefix equal to prefix[j] - k exists. Counting prefixes turns every O(n) range check into an O(1) dictionary lookup: one pass, O(n) total.

The problem

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals k.

Hints

• Brute force is O(n^2). The trick is using prefix sums.
• If prefix[j] - prefix[i] == k, then subarray (i,j] sums to k.
• Store prefix sum counts in a map. For each position, check if (prefix - k) was seen.
• Initialize map with {0: 1} to handle subarrays starting from index 0.

Test cases

Reference starter code

from collections import defaultdict

def subarray_sum(nums, k):
    # Prefix sum + hash map approach
    pass

print(subarray_sum([1, 1, 1], 2))       # 2
print(subarray_sum([1, 2, 3], 3))       # 2
print(subarray_sum([-1, -1, 1], 0))     # 1

More challenges in this topic

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.