Optimization for O(n^2) Python


  • 0
    J

    a simple optimization for the concise python solution:

    result = []
            nums.sort()
            x1_idx = 0
            limit = len(nums) - 2
            while(x1_idx < limit):
                k = limit + 1
                j = x1_idx + 1
                x1 = nums[x1_idx]
                x2 = nums[j]
                x3 = nums[k]
                while(1):              
                    Sum = x1 + x2 + x3
                    if(Sum == 0):
                        result.append([x1, x2, x3])
                        while(j < k and nums[k-1] == x3):
                            k -= 1
                        k -= 1
                        while(j < k and x2 == nums[j + 1]):
                            j += 1
                        j += 1
                        if(j < k):
                            x2 = nums[j]
                            x3 = nums[k]
                        else:break
                    elif(Sum > 0):
                        while(j < k and nums[k-1] == x3):
                            k -= 1
                        k -= 1
                        if(j < k):
                            x3 = nums[k]
                        else:break
                    else:
                        while(j < k and x2 == nums[j + 1]):
                            j += 1
                        j += 1
                        if(j < k):
                            x2 = nums[j]
                        else:break
                while(x1_idx < limit and x1 == nums[x1_idx+1]):
                    x1_idx += 1
                x1_idx += 1
                
            return result
    

Log in to reply
 

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