leetcode 最接近的三数之和 python

待我称王封你为后i 2022-03-28 06:42 140阅读 0赞

[题目链接][Link 1]  
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。  
![在这里插入图片描述][20190109202149155.png]

--------------------

## 思路 ##

遍历三个数字，一个数字顺序遍历，另外两个采用二分法遍历

--------------------

## 代码 ##

class Solution:
        def threeSumClosest(self, nums, target):
            """ :type nums: List[int] :type target: int :rtype: int """
            if len(nums) < 3:
                raise Exception('input error')
            nums.sort()
            threeNums = nums[0] + nums[1] + nums[2]
            differ = abs(threeNums - target)
            ans = threeNums
            for i in range(len(nums) - 2):
                low = i + 1
                high = len(nums) - 1
                while(low < high):
                    threeNums = nums[i] + nums[low] + nums[high]
                    if abs(threeNums - target) < differ:
                        differ = abs(threeNums - target)
                        ans = threeNums
                    if threeNums == target:
                        return target
                    elif threeNums < target:
                        while low < high and nums[low + 1] == nums[low]:
                            low += 1
                        low += 1
                    else:
                        while low < high and nums[high - 1] == nums[high]:
                            high -= 1
                        high -= 1
            return ans

[Link 1]: https://leetcode-cn.com/problems/3sum-closest/
[20190109202149155.png]: /images/20220328/b0b891ffdaab4484b9bbe98d24e25654.png