LeetCode 3Sum Closest

LeetCode解題之3Sum Closest

原題

找出一個列表中三個元素之和與目標值最接近的情況，並返回這個值。假設整個列表中只有一個最接近的值。

注意點：

例子：

輸入: nums=[1, 1, 1, 1], target=-100
輸出: 3

解題思路

思路與3Sum基本相同，現在要額外維護一個表示之前三元組中與目標值的差最小值的變量，這個變量的初始化值應該很大，防止把有意義的三元組直接排除了。此外，由於題目中明確說只有唯一的一組最優解，所有不用考慮重復數字了。

AC源碼

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        i = 0
        result = 0
        # Init the distance between result and target with a very large number
        distance = pow(2, 32) - 1
        for i in range(len(nums)):
            j = i + 1
            k = len(nums) - 1
            while j < k:
                l = [nums[i], nums[j], nums[k]]
                if sum(l) == target:
                    return target
                if abs(sum(l) - target) < distance:
                    result = sum(l)
                    distance = abs(sum(l) - target)
                elif sum(l) > target:
                    k -= 1
                else:
                    j += 1
        return result


if __name__ == "__main__":
    assert Solution().threeSumClosest([1, 1, 1, 1], -100) == 3

歡迎查看我的Github來獲得相關源碼。