Given an integer array nums, return every unique triplet [nums[i], nums[j], nums[k]] with i, j, k all different whose sum is 0. The result must not contain the same triplet twice. The triplets and the numbers inside them may be in any order.
-1 + -1 + 2 = 0 and -1 + 0 + 1 = 0. Using the other -1 gives the same triplets, so they are listed once.- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force checks every triple in O(n^3) and then deduplicates. After sorting, fix the smallest element nums[i]; the other two must sum to -nums[i], which is exactly the sorted two-pointer problem, O(n) per i. Sorting also makes duplicates sit next to each other, so we can skip a value we have already used as the first element, and skip repeated values after finding a triplet. That gives O(n^2) with no extra set.
Algorithm
- Sort
nums. - For each
i, skip it ifnums[i] == nums[i-1]. Ifnums[i] > 0, stop: no triplet can sum to 0. - Set
l = i + 1,r = n - 1. Whilel < r, computes = nums[i] + nums[l] + nums[r]. - If
s < 0,l++; ifs > 0,r--. - If
s == 0, record the triplet, then movelandrinwards past any repeated values.
O(n^2)Space: O(1) extra besides sorting and the outputi by comparing with the previous element (not the next), and after a match skip duplicates of both l and r.class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() ans = [] n = len(nums) for i in range(n - 2): if nums[i] > 0: break # smallest is positive: done if i > 0 and nums[i] == nums[i - 1]: continue # same first value as before l, r = i + 1, n - 1 while l < r: s = nums[i] + nums[l] + nums[r] if s < 0: l += 1 elif s > 0: r -= 1 else: ans.append([nums[i], nums[l], nums[r]]) l += 1 r -= 1 while l < r and nums[l] == nums[l - 1]: l += 1 # skip repeated values while l < r and nums[r] == nums[r + 1]: r -= 1 return ans