Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
Example:
Given nums = [-1, 0, 1, 2, -1, -4]
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Idea
Sort first
fix the smallest element, loop from left to right
to find the second and third element, similar to Two Sum II - Input array is sorted _Q167
Time complexity
O(n^2)
space complexity
O(1)
Solution
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
nums.sort()
for i in xrange(len(nums)-2):
# to avoid duplicate for i
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l +=1
elif s > 0:
r -= 1
else:
res.append((nums[i], nums[l], nums[r]))
# to avoid duplicate for l
while l < r and nums[l] == nums[l+1]:
l += 1
# to avoid duplicate for r
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1; r -= 1
return res