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
- Input
nums = [-1, 0, 1, 2, -1, -4]
- Output
[[-1, -1, 2], [-1, 0, 1]]
- 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 · every language run against every case
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