Given an array of integers, are there elements in such that ? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array ,
A solution set is:
The idea behind the presented algorithm is to sort the array in ascending order first. Once the array is sorted we can iterate over the elements using two loops which gives us an time complexity.
Since we need to find three elements such that , we will use the outer iteration to fix . For the rest of the elements and we will use an inner-loop with two pointers:
• A incrementing pointer, , starting at
• A decrementing pointer, , starting at
If the is equal to , we have found ourselves a valid pair.If we have to increment . We do this by increasing (remember our array is sorted). If we need to decrement by moving to the left.
We will also do some skipping of adjacent elements that are equal in order to avoid duplicate pairs.
class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ nums = sorted(nums) ans =  for i in range(0,len(nums)-1): if i==0 or (nums[i-1]!=nums[i]): l = i + 1 r = len(nums) - 1 while r > l: s = nums[i] + nums[l] + nums[r] if s == 0: ans.append([nums[i], nums[l], nums[r]]) l += 1 r -= 1 # Skip duplicates while l
nums[r] --> we need to increase l (in order to decrease |nums[i] + nums[l]| # since nums[r] would only get smaller if we were to decrease r) l += 1 else: r -= 1 return ans def main(): solution = Solution() print(solution.threeSum([-1,0,1,2,-1,-4])) print(solution.threeSum([0,0,0,0])) if __name__ == "__main__": main()