How do you count the number of contiguous subarrays whose sum equals a given target?
You keep a running total and you remember the totals you have already seen, because the answer is the difference between two of them.
So here is the idea. The sum of the stretch from position a to position b is the running total at b minus the running total at a minus one. So if you are at position b with a running total of s, and you want a stretch that adds up to k, then you are looking for a running total of s minus k that you have already passed.
def subarray_sum(nums, k):
counts = {0: 1}
total = 0
found = 0
for value in nums:
total += value
found += counts.get(total - k, 0)
counts[total] = counts.get(total, 0) + 1
return found
So how does it work? The dictionary holds every running total you have seen so far and how many times you have seen it. For each value you add it to the running total, and then you ask the dictionary how many times you have seen the running total minus k. That is the number of stretches that end here and add up to k.
And there is one line that looks strange and is not. The dictionary starts with {0: 1}, and that is what counts the stretches that begin at the very first value. Without it, a stretch that starts at position zero would never be counted.
The next two questions in this topic show the same idea written out again.