O(N^2) Python with upper/lower/duplicate checks


  • 0
        def threeSum(self, nums):
            res = []
            nums.sort()
            
            for i in range(len(nums) - 2):
                if sum(nums[i:i+3]) > 0: break # lower bound check
                elif nums[i] + nums[-1] + nums[-2] < 0: continue # upper bound check
                    
                if i and nums[i] == nums[i-1]: continue # duplicate check
                    
                L, R = i+1, len(nums)-1
                while L < R:
                    if L == i+1 or nums[L] > nums[L-1]: # duplicate check
                        if nums[i] + nums[L] + nums[R] == 0: 
                            res.append([nums[i], nums[L], nums[R]])
                        elif nums[i] + nums[L] + nums[R] > 0:
                            R -= 1
                            continue
                    L += 1
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.