【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
        for i in xrange(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
            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
                    right -= 1
        return result

Log in to reply

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