301. Is There a Zero-Sum Stretch
Core1000 ms256 MBSolved by 0%
Print Yes if some contiguous stretch of the array sums to exactly zero, and
No otherwise.
Checking every stretch is quadratic. Prefix sums make it a membership question: a stretch sums to zero exactly when the running total is the SAME at both of its ends, so the answer is Yes as soon as a running total repeats.
Seed the set with 0 before starting, standing for the empty prefix. Without it a
stretch that begins at index 0 is missed, and a lone 0 in the array is missed
too.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n integers.
Output
Print Yes or No on one line.
Input5
4 2 -3 1 6
OutputYes
Notehas a zero-sum stretch in the middle
Input3
1 2 3
OutputNo
Noteis all positive, so no stretch can sum to zero
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.