134. Trios to Zero
A ledger clerk records daily balance changes in the array nums, where gains are positive and losses are negative. An auditor wants to know which groups of three entries cancel each other out exactly.
Return every distinct triple of values [a, b, c] such that a + b + c = 0, where the three entries come from three different positions of nums. Two triples are the same if they contain the same values, regardless of order, and each such triple must be listed only once. The triples may be returned in any order, and so may the values inside each triple. If no triple adds up to zero, return an empty array.
Example 1
- Input:
- nums = [-4,-1,0,1,2,5]
- Output:
- [[-4,-1,5],[-1,0,1]]
- Explanation:
-4+(-1)+5=0 and -1+0+1=0 are the only zero-sum triples.
Example 2
- Input:
- nums = [3,-3,0,0,0]
- Output:
- [[-3,0,3],[0,0,0]]
- Explanation:
The value 0 is used three times (three different positions) and gives [0,0,0]. The pair 3 and -3 needs a third 0, giving [-3,0,3]. Each distinct triple is reported once.
Example 3
- Input:
- nums = [1,2,4]
- Output:
- []
- Explanation:
All entries are positive, so no triple can sum to zero.
Constraints
1 ≤ nums.length ≤ 2000
-107 ≤ nums[i] ≤ 107
How this problem is judged
- Answers
- Lists at every level may be in any order. Duplicates still count.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(1) extra, apart from sorting and the output