Python O(N^2) beats 100%


  • 0
    K
    class Solution(object):
        def threeSumClosest(self, nums, target):
            nums.sort()
            length=len(nums)
            result=nums[0]+nums[1]+nums[2]
            if(length==3):
                return result
            for i in xrange(length):
                j=i+1
                k=length-1
                if(i<length-3 and (nums[i]+nums[j]+nums[j+1])>target):
                    return result
                if(i< k-1 and (nums[i]+nums[k-1]+nums[k]) < target):
                    result=nums[i]+nums[k-1]+nums[k]
                    continue
                while(j<k):
                    sum=nums[i]+nums[j]+nums[k]
                    if(sum==target):
                        return sum
                    elif(sum<target):
                        j+=1
                    else:
                        k-=1
                    if(abs(sum-target)<abs(result-target)):
                        result=sum
            return result
    

Log in to reply
 

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