【Python】Beating 95% solution with two pointers【O(N ^ 2)】


  • 6

    Same algorithm as 3sum problem, where we sort nums, then use two pointers to check all the possible combinations, while fixing one element.

    In this problem, we just need to add a new variable diff to track the difference between target and current best result. In addition, we move the pointers in terms of diff (be careful with the sign)

    def threeSumClosest(self, nums, target):
        result, diff = 0, sys.maxint
        nums.sort()
        
        for i in xrange(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            left, right = i + 1, len(nums) - 1
            
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                hold_diff = abs (total - target)
                
                if not hold_diff:
                    return total
                    
                if hold_diff  < diff:
                    result = total
                    diff = hold_diff
                    
                if total < target:
                    left += 1
                
                else:
                    right -= 1
                    
        return result

Log in to reply
 

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