You are given a list of integers nums. Return every triple of values [a, b, c] with
a + b + c = 0, where the three values come from three different positions in nums.
List each triple of values only once: two triples holding the same three values (in any order) count as the same. Return the triples in any order, with the values inside each triple in any order.
Example 1
- Input
- nums = [-3, 1, 2, 0, -1, 3]
- Output
- [[-3, 0, 3], [-3, 1, 2], [-1, 0, 1]]
Example 2
- Input
- nums = [2, -1, -1, 0]
- Output
- [[-1, -1, 2]]
-1s sit at different positions, so a triple can use both.Example 3
- Input
- nums = [0, 0, 0, 0]
- Output
- [[0, 0, 0]]
0, 0, 0, but it is listed once.Constraints
numsholds 3 to 3000 numbers.- Every number is between −10⁵ and 10⁵.
Show the pattern
Two pointers
Fix one number and the rest is a pair-sum search. Sorting first lets two pointers find every pair in one sweep, and puts equal values side by side so repeated triples are easy to skip.
See two pointers in a visualiserShow the approach
Sort a copy of the list. For each position i, let nums[i] be the smallest value of the
triple. Skip it if it equals nums[i − 1], since that value has already been tried. Then search
the part after i with two pointers, left = i + 1 and right = n − 1, for pairs summing to
−nums[i]: a sum that is too small moves left right, too big moves right left. On a match,
record the triple, then move left past every copy of its value (and right likewise) so the
same triple isn't recorded twice.
Once nums[i] is greater than 0 you can stop: three positive numbers can't sum to zero.
Time: O(n²) · Space: O(n) for the sorted copy, besides the output