A little optimize O(n*n) solution use python


  • 0
    N
    class Solution(object):
        def threeSumClosest(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            if not nums or len(nums) < 3:
                return None
            
            "sort the nums"
            nums.sort()
            
            "traverse the nums"
            ret = nums[0] + nums[1] + nums[2]
            for i in xrange(len(nums) - 2):
                "filter duplicate compute"
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                "compute from i+1 to len(nums) - 1"
                j, k = i + 1, len(nums) - 1
                while j < k:
                    total = nums[i] + nums[j] + nums[k]
                    if total == target:
                        return total
                    if abs(total - target) < abs(ret - target):
                        ret = total
                    if total < target:
                        j += 1
                    elif total > target:
                        k -= 1
            
            return ret
    

Log in to reply
 

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