Why my python solution using sort and binary search got a TLE?


  • 1
    J
    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            res = []
            nums.sort()
            l = len(nums)
            for i in range(l):
                for j in range(i+1, l):
                    target = 0-nums[i]-nums[j]
                    if binary_search(nums, target, j+1):
                        item = [nums[i], nums[j], target]
                        if item not in res:
                            res.append(item)
            return res
    
    
    def binary_search(l,key,lo=0,hi=None):
        if not hi:  
            hi = len(l)  
        while lo<hi:  
            mid = (lo+hi)/2
            if l[mid]>key:  
                hi = mid
            elif l[mid]<key:  
                lo = mid+1 
            else:
                return mid
        return None

  • 0
    J

    @Jack_Xiao I know the reason now, I didn't get rid of the repeated ones.


Log in to reply
 

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