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
classSolution(object):defthreeSum(self,nums):""" :type nums: List[int] :rtype: List[List[int]] """ res = [] nums.sort()for i inxrange(len(nums)-2):# to avoid duplicate for iif i >0and nums[i]== nums[i-1]:continue l, r = i+1,len(nums)-1while l < r: s = nums[i]+ nums[l]+ nums[r]if s <0: l +=1elif s >0: r -=1else: res.append((nums[i], nums[l], nums[r]))# to avoid duplicate for lwhile l < r and nums[l]== nums[l+1]: l +=1# to avoid duplicate for rwhile l < r and nums[r]== nums[r-1]: r -=1 l +=1; r -=1return res