Python 52ms (100%) with explanation


  • 0
    J

    The solution is not very elegantly written but it does the jobs. I just want to point out few lines (marked with "### see this ###" in the code below) that improves the speed further, compared to brute force O(N^2) answers.

    The steps:
    (0) if the target is <=0, sort the array, otherwise I sort the array reversely so it's from large to small.
    (1) for 3 numbers with index i,j,k, I loop i through 0, 1, 2.. len(nums)
    (2) then loop j from i+1, i+2.., meanwhile loop k through len(nums)-1, len(nums)-2.. until j==k
    (3) break the i loop once nums[i] > 0 (in the case of target > 0, nums[i] <0), since at this point, all 3 numbers will be positive and can no longer return any sum that's smaller than previously obtained smallest (since they have negative numbers plus all the positive number you have now).

    class Solution(object):
        def threeSumClosest(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            nums.sort()
            if target <= 0:### see this ###
                out = abs(sum(nums[:3])-target)
                out_sum = sum(nums[:3])
                n=len(nums)
                for i in xrange(n):
                    j,k=i+1,n-1
                    while j<k:
                        isum=nums[i]+nums[j]+nums[k]
                        if abs(isum-target) < out:
                            out = abs(isum-target)
                            out_sum = isum
                        if isum > target:
                            k-=1
                        elif isum < target:
                            j+=1
                        elif isum==target:
                            return isum
                    if nums[i]>0:### see this ###
                        return out_sum
                return out_sum
            if target > 0:  ### see this ###
                nums = nums[::-1]### see this ###
                out = abs(sum(nums[:3])-target)
                out_sum = sum(nums[:3])
                n=len(nums)
                for i in xrange(n):
                    j,k=i+1,n-1
                    while j<k:
                        isum=nums[i]+nums[j]+nums[k]
                        if abs(isum-target) < out:
                            out = abs(isum-target)
                            out_sum = isum
                        if isum < target:
                            k-=1
                        elif isum > target:
                            j+=1
                        elif isum==target:
                            return isum
                    if nums[i]<0:### see this ###
                        return out_sum
                return out_sum
    

Log in to reply
 

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