Medium Sort + Two Pointer Two Pointers
In plain English: Find all unique sets of three numbers in the array that add up to zero.
Sort the array, fix one element, then use two pointers on the remainder to find pairs summing to the negative of the fixed element. Skip duplicates at each level to avoid repeated triplets.
Prompt
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] == 0.
Try to write it from scratch before scrolling down.
Solution
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue # skip duplicate fixed element
l, r = i + 1, len(nums) - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total == 0:
result.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1 # skip duplicates
while l < r and nums[r] == nums[r-1]:
r -= 1 # skip duplicates
l += 1; r -= 1
elif total < 0:
l += 1
else:
r -= 1
return result
# Test: three_sum([-1,0,1,2,-1,-4]) == [[-1,-1,2],[-1,0,1]]
# Test: three_sum([0,0,0]) == [[0,0,0]]