3Sum

Two Pointer

Problem

Given an array of unsorted numbers, find all unique triplets in it that add up to zero.

For example:

Input: [-3, 0, 1, 2, -1, 1, -2]
Output: [-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]

Input: [-5, 2, -1, -2, 3]
Output: [[-5, 2, 3], [-2, -1, 3]]

Solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        lis =[]
        nums.sort()
        for i in range(len(nums)-2):
            j = i+1
            k = len(nums)-1
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            while ( j < k):
                s = nums[i]+nums[j]+nums[k]
                
                if s == 0:
                    lis.append((nums[i],nums[j],nums[k]))
                    j = j+1
                    k = k-1
                    while j < k and nums[j] == nums[j-1]:
                        j+=1
                    while j < k and nums[k] == nums[k+1]:
                        k-=1
                    
                elif s > 0:
                    k = k-1        
                elif s < 0:
                    j = j+1            
        
        return lis