3Sum (Leetcode 15)

Problem Link: https://leetcode.com/problems/3sum/

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n=len(nums)
        ans=[]
        start=0
        while(start<n-2):
            
            middle=start+1
            end=n-1
            
            while(middle<end):
                tempSum=nums[middle]+nums[end]
                if(tempSum==-1*(nums[start])):
                    tempAns=[nums[start],nums[middle],nums[end]]
                    ans.append(tempAns)
                    
                    #remove duplicates
                    while(middle+1<end and nums[middle]==nums[middle+1]):
                        middle+=1
                    middle+=1
                    while(end-1>=0 and nums[end]==nums[end-1]):
                        end-=1
                    end-=1
                    
                elif(tempSum<-1*(nums[start])):
                    
                    # remove duplicates
                    while(middle+1<end and nums[middle]==nums[middle+1]):
                        middle+=1
                    middle+=1
                else:
                    
                    # remove duplicates
                    while(end-1>=0 and nums[end]==nums[end-1]):
                        end-=1
                    end-=1
                    
            # remove duplicates            
            while(start+1<n-2 and nums[start]==nums[start+1]):
                start+=1
            start+=1
            
        return ans
                    
                    
        

Last updated