Subarray Sum Equals K
Count subarrays whose sum equals k.
Pattern fit
The sum of a subarray is the difference of two prefixes, so the question becomes: how many earlier prefixes equal currentPrefix - k?
Key observation
The hash map stores counts of past prefix sums, not intervals themselves.
Target complexity
O(n) / O(n)
How to break down the solution cleanly
The sum of a subarray is the difference of two prefixes, so the question becomes: how many earlier prefixes equal currentPrefix - k?
The hash map stores counts of past prefix sums, not intervals themselves.
Define what the cumulative state means.
Build the prefix in one forward pass.
Reference implementation
Python# Generic pattern template
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
range_sum = prefix[r + 1] - prefix[l]
Common pitfalls
Updating the current prefix count before querying it.
Trying to use sliding window when negatives exist.
Common follow-ups
Why does a sliding window fail when negatives are present?
How would you adapt this to divisibility or modulo conditions?
Continue with related problems
Build repeatable depth inside the Prefix Sum cluster before moving on.