112. Subarrays That Sum to Zero
Challenge1000 ms256 MBSolved by 0%
Print how many contiguous subarrays have a sum of exactly zero.
Subarrays that overlap each other all count separately.
Constraints - `1 ≤ n ≤ 200000` - `-1000 ≤ a[i] ≤ 1000` - the answer always fits in a signed 64 bit integer
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print one integer, how many contiguous subarrays sum to exactly zero.
Input5
1 -1 2 -2 3
Output3
Notehas three zero-sum subarrays, one of which spans four elements
Input3
1 2 3
Output0
Notehas no zero-sum subarray at all
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.