Counting the stretches that add up to k

You have a list of numbers. How many runs of numbers in a row add up to exactly k? In the last lesson, prefix sums gave the sum of any run with one subtraction. Now that becomes a way to count runs. This is the first task where you need "how many runs have this property" instead of one sum. The slow way tries every start and every end, which is O(n²). The prefix-sum way counts all the runs in one pass. It even works with negative numbers, where a sliding window quietly gives wrong answers.

Take the test list [3, 4, 7, 2] and k = 7. Write down the running total after each number: 3, 7, 14, 16. Before the first number the total is 0. You want every run of numbers in a row that adds up to 7.

You never add anything up again. After each number, check whether the total "current total minus 7" appeared earlier. After the 2nd number the total is 7, so you look for 0: that is the total before the first number, and it appeared. So the numbers 3 and 4 add up to 7. After the 3rd number the total is 14, so you look for 7: it appeared after the 2nd number. So the number 7 on its own adds up to 7. After the 4th number the total is 16, so you look for 9: it never appeared.

So you keep a record of which totals have appeared and how many times. The answer, 2 here, builds up during one pass.

Walk the list and keep a running total. After each number it equals the prefix sum of that position. The sum of any run is the difference of two prefix sums: the sum at its end minus the sum right before its start. So a run adds up to k exactly when some earlier prefix sum equals the current sum minus k. That gives the number of good runs that end at the current position: it is how many times the prefix sum sum - k appeared earlier.

To answer at once, keep a map from a prefix-sum value to how many times it has appeared. At each element, add it to sum, look up how many times sum - k has appeared, and add that to the count. Then record the current sum in the map. Start the map with {0: 1}. Before the first element the sum is 0 (the empty start of the list). This entry lets a run that begins at the very start of the list be counted too.

Trace [1, 2, 3] with k = 3. Start: seen = {0: 1}, sum = 0, count = 0.

• Element 1: sum = 1. Look for 1 - 3 = -2: never seen, +0. Record it: seen = {0:1, 1:1}.
• Element 2: sum = 3. Look for 3 - 3 = 0: seen once, +1, and count becomes 1. Record 3:1.
• Element 3: sum = 6. Look for 6 - 3 = 3: seen once, +1, and count becomes 2. Record 6:1.

The answer is 2: the runs [1, 2] and [3].

Time is O(n): one pass, and each lookup and each write in the map costs O(1) on average. Memory is O(n) for the map in the worst case, when all prefix sums are different. That beats the double loop at O(n²): a little memory in exchange for a whole factor of n in time. The sliding window of the earlier lessons needs non-negative numbers. This method doesn't: negative numbers and zeros need no extra code. It compares prefix sums and never grows or shrinks a window.

Counting the periods when the balance in a log of transactions did not change (the changes add up to zero). Runs of a signal whose sum equals a target. Subarrays with a given XOR (the same method, with XOR in place of the sum). How many times a metric came back to an earlier level. The idea "prefix sum plus a map" works beyond sums. If a property of a range equals the difference of two running values, you can count or find such ranges in one pass. All you need is to remember the running values you have already seen. A whole family of tasks of the form "count the subarrays where..." is solved this way.