Count stretches that hit k
Count every run of numbers that adds up to k, with a map of running totals. About 10 minutes.
Look up the partner total
You want stretches that add up to exactly k. A stretch ending here adds up to k when the running total now, minus the running total just before the stretch started, is k. So the total you're looking for back in the past is: now minus k.
That's the two-sum idea again: instead of searching, keep the totals you've seen in a map and look up the partner.
total 1. Partner 1 − 2 = −1: seen 0 times. Store 1.
Count partners, don't just find one
Several earlier positions can have the same running total, and each one starts a different stretch. So the map counts how many times you've seen each total, and you add that count.
Two details: start the map with the total 0 seen once (the empty start before the first box), and look up before you store the current total. Otherwise, when k is 0, an empty stretch would sneak into the count.
seen = {0: 1}
total = count = 0
for x in nums:
total += x
count += seen.get(total - k, 0)
seen[total] = seen.get(total, 0) + 1
return countk is 3. The running total is 10, and the map says the total 7 was seen twice. How many stretches ending here add up to 3?
- A2
- B1
- C10
Show the answer
2. Each earlier total of 7 starts a stretch that adds 10 − 7 = 3.
Stretches that sum to k
You get a list of numbers (possibly negative) and a target k. Count the non-empty runs of consecutive numbers that add up to exactly k, and return the count.
nums = [1, 2, 3], k = 3 → 2
0 ≤ n ≤ 1,000,000 · −1,000 ≤ each value ≤ 10^6 · the count can pass 2^31: return a long