Hashing is the pattern you reach for when brute force keeps asking, "Have I seen the matching value before?" Prefix sum is the version for subarrays, where the matching value is a previous running sum.
Pattern Table
| Signal | Use | Lesson |
|---|---|---|
| Find complement | Hash map value to index | Two Sum |
| Count repeated symbols | Frequency map | Valid Anagram |
| Longest consecutive run | Hash set sequence starts | Longest Consecutive Sequence |
| Subarray target sum | Prefix sum frequency | Subarray Sum Equals K |
Core Formula
currentPrefix - previousPrefix = target
previousPrefix = currentPrefix - targetFAQs
Why not use sliding window for every subarray sum?
Sliding window needs monotonic movement. Negative numbers break that, while prefix sums still work.
What is the most common hashing mistake?
Updating the map before checking the current value when the problem requires earlier elements only.