The problem
Given an integer array nums, return every triplet [nums[i], nums[j], nums[k]] of three different positions whose values add up to 0.
The answer must not contain the same triplet twice (the same three values in any order count as the same).
Examples
01
- Input
nums = [-1, 0, 1, 2, -1, -4]
- Output
[[-1, -1, 2], [-1, 0, 1]]
02
- Input
nums = [0, 1, 1]
- Output
[]
Constraints
- 3 ≤ nums.length ≤ 3000
- −10⁵ ≤ nums[i] ≤ 10⁵
The idea
Sort the array. Then fix the first number nums[i]: what remains is Two Sum II on the rest of the array — find two numbers adding to −nums[i] — which two pointers solve in one pass.
Duplicates are skipped at both levels: if nums[i] equals the previous first number, it would find the same triplets, so skip it; after recording a triplet, move l past copies of the same value. And once nums[i] is positive, three numbers at least that large cannot sum to 0, so stop.
- Time
- O(n²) — n choices of the first number, one linear scan each
- Space
- O(1) extra (besides sorting and the output)
Solution
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() out = [] for i in range(len(nums) - 2): if nums[i] > 0: break # the smallest of the three is positive: no more zero sums if i > 0 and nums[i] == nums[i - 1]: continue # same first number as before: same triplets l, r = i + 1, len(nums) - 1 while l < r: total = nums[i] + nums[l] + nums[r] if total < 0: l += 1 elif total > 0: r -= 1 else: out.append([nums[i], nums[l], nums[r]]) l += 1 while l < r and nums[l] == nums[l - 1]: l += 1 # skip repeats of the middle number return out