Prefix sums
Keep a running total as you go. The sum of any run of items is just the total at its end minus the total before its start. So for each new total, ask one question: have I seen a total exactly target less than this?
34162572
Find items in a row that add up to 13. Press play or step forward to start.
1function subarrayWithSum(a, target) {2 const seen = new Map([[0, -1]]);3 let prefix = 0;4 for (let i = 0; i < a.length; i++) {5 prefix += a[i];6 if (seen.has(prefix - target)) {7 return [seen.get(prefix - target) + 1, i];8 }9 seen.set(prefix, i);10 }11 return null;12}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | the first item is the target |
| average | n | one pass, one lookup per item |
| worst | n | no run matches: every item is read once |
| space | n | one stored total per item |
Where it breaks
- Forgetting the starting 0. The map starts with a total of 0 before index 0. Leave it out and any run that starts at the very first item is missed. Pick Whole array: the match is that starting 0.
- Trying every start and end. Checking every run costs about n²/2 sums. The running total answers the same question in one pass, at the price of storing n totals.
- Negative values are fine here. Unlike the variable sliding window, this never assumes adding an item makes the sum grow. That is why it is the go-to method when values can be negative.