Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.
The output should not contain any duplicate triplets. You may return the output and the triplets in any order.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = [0,1,1]
Output: [] Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Sort array first - makes it easier to Skip duplicates and Use two pointers
2 nested loops:
- Outer loop fixes first number
- Two pointers find pairs that sum to its negative
Skip duplicates in three places:
For first number (outer loop)
For second number (left pointer)
For third number (right pointer)
Time: O(n²)
Space: O(1)
In [15]:
def threesum(nums,target):
nums.sort()
res=[]
# Fix first number, then use two pointers for remaining sum
for i in range(len(nums)-2):
# Skip duplicates for first number
if i>0 and nums[i]==nums[i-1]:
continue
l=i+1
r=len(nums)-1
while l<r:
if nums[i]+nums[l]+nums[r]==target:
res.append([nums[i],nums[l],nums[r]])
# Skip duplicates for second number
while l < r and nums[l] == nums[l+1]:
l += 1
# Skip duplicates for third number
while l < r and nums[r] == nums[r-1]:
r -= 1
l+=1
r-=1
elif nums[i]+nums[l]+nums[r] < target:
l+=1
else:
r-=1
return res
In [16]:
threesum([-1,0,1,2,-1,-4],0)
Out[16]:
[[-1, -1, 2], [-1, 0, 1]]
In [17]:
threesum([-2,-2,1,1,1,1,1,-2],0)
Out[17]:
[[-2, 1, 1]]
In [18]:
threesum([0,0,0],0)
Out[18]:
[[0, 0, 0]]
In [19]:
a=[-1,0,1,2,-1,-4]
a.sort()
print(a)
[-4, -1, -1, 0, 1, 2]