Description
Find all distinct value triplets at different indices that sum to zero. Output order is irrelevant.
Solution
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums)-2):
if i and nums[i] == nums[i-1]:
continue
left, right = i+1, len(nums)-1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[-2,0,1,1,2]]- Output
[[-2,0,2],[-2,1,1]]
Only the two displayed distinct triplets sum to zero.
Example 2
- Input
[[0,0,0,0]]- Output
[[0,0,0]]
Repeated indices create only one unique value triplet.
Example 3
- Input
[[1,2,3]]- Output
[]
All values are positive, so no triple sums to zero.
Approach
Sort, fix one value, and use two pointers for the remaining sum. Skip duplicates after each match.
Time & space
O(n²) time; O(n) sorting workspace in Python, excluding output. Here n is the input length.