Algorithms and Data Structures · Middle · Question 57 of 75
Subarray sum equals k: why do we store counts of prefix sums in a hash map?
- 1To avoid computing prefix sums at all
- 2To sort the prefix sums for a later binary search
- ✓Correct answer: A subarray ending here sums to k if
prefix - kwas seen
Explanation
The sum of (i, j] equals prefix[j] - prefix[i]. For each position, add how many earlier prefixes equal prefix - k. One pass, O(n), and it works with negative numbers, unlike a sliding window.