Same total twice
Spot a stretch that sums to zero by remembering every running total. About 9 minutes.
Back where you started
You go on a hike with a step counter that shows height gained and lost. At some point the display reads exactly what it read an hour ago. Whatever you climbed and descended in that hour cancelled out: it added up to 0.
Running totals work the same way. If the total after some box equals a total you had earlier, the numbers in between sum to zero.
total 4. Seen {0}? No. Add 4.
Remember every total in a set
Walk the array, keeping a running total, and store every total you reach in a set. Each new total asks one question: have I been here before?
Put 0 in the set before you start, standing for "before the first box". Otherwise a stretch that starts right at the beginning, like 3 then −3, would be missed.
seen = {0}
total = 0
for x in nums:
total += x
if total in seen:
return True
seen.add(total)
return FalseThe numbers are 3, −3, 5, and the set starts with just 0. When is a repeat found?
- AAfter the −3 (the total is 0 again)
- BNever
- CAfter the 5
Show the answer
After the −3 (the total is 0 again). 0 is already in the set, so 3 + (−3) = 0 is found.
Zero-sum stretch
You get a list of numbers. Return true if some non-empty run of consecutive numbers adds up to exactly 0. Otherwise return false.
nums = [4, 2, -3, 1, 6] → true
0 ≤ n ≤ 1,000,000 · −10^6 ≤ each value ≤ 10^6