How many triples add to zero
MediumStuck?
Show a hintHide the hint
Sort first. Then fix each value in turn and find pairs in the rest with one index at each end, skipping over any value equal to the one just used.
The idea behind this problem
Next in this lesson
Shortest stretch that reaches the targetCount the distinct triples of values from the list that add up to zero.
Two triples are the same if they use the same three values, whatever order they were found in. Each value may be used once per triple, at the position it sits in.
Worked example#
For [-1, 0, 1, 2, -1, -4], sort it first: [-4, -1, -1, 0, 1, 2].
Now fix the leftmost value and look for a pair in the rest that cancels it, using one index at each end of the remaining stretch:
| fixed | need | left | right | sum of pair | move |
|---|---|---|---|---|---|
| -4 | 4 | -1 | 2 | 1 | too small, left moves in |
| -4 | 4 | -1 | 2 | 1 | too small, left moves in |
| -4 | 4 | 0 | 2 | 2 | too small, left moves in |
| -4 | 4 | 1 | 2 | 3 | too small, ends meet, done |
| -1 | 1 | -1 | 2 | 1 | found: (-1, -1, 2) |
| -1 | 1 | 0 | 1 | 1 | found: (-1, 0, 1) |
| -1 | ... | same as the previous fixed value, skip it | |||
| 0 | 0 | 1 | 2 | 3 | too large, right moves in, ends meet |
Two distinct triples.
Sorting is what makes this work. Once sorted, a sum that is too small can only be fixed by moving the left index up, and one that is too large only by moving the right index down, so each pair search is a single pass instead of a nested loop. Sorting is also what makes duplicates easy: identical values sit together, so skipping a repeat is one comparison.
Constraints#
3 <= n <= 3000-100000 <= nums[i] <= 100000
Input
nums is a count then that many integers.
Output
The number of distinct triples that sum to zero.
Examples
Input
6 -1 0 1 2 -1 -4
Output
2
The triples are (-1, -1, 2) and (-1, 0, 1).
Input
3 0 1 1
Output
0
No three of these add to zero.
Input
4 0 0 0 0
Output
1
Only one distinct triple exists, all zeros, however many zeros there are.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.