16. 最接近的三数之和

题干

给定一个包括 个整数的数组 和 一个目标值 。找出 中的三个整数，使得它们的和与 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和target = 1.

与 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题和前一道题思路基本相同，固定一个值再使用双指针法计算另外两个值。

双指针法的流程以及解释已经在上一篇文章中介绍了，这里不再细说，

感兴趣可以移步上一篇文章，文章名：15. 三数之和。

本题的特别之处知识将存储三元组改为存储最接近taiget的值即可

Python代码

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        res = 2 ** 31 -1 + target
        for index in range(len(nums) - 2):
            i, j = index + 1, len(nums) - 1
            value = nums[index]
            while i < j:
                sum = value + nums[i] + nums[j]
                if abs(sum - target) < abs(res - target): res = sum
                if sum > target: j -= 1
                elif sum < target: i += 1
                else:
                    return target
        return res

进一步优化

在评论区中有大佬对头指针的选取采用了二分法，直接定位到最接近的位置，时间复杂度会有些提升，参考代码

参考代码:

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        res = 2 ** 31 -1 + target
        end = len(nums) - 1
        for index in range(len(nums) - 2):
            i = max(index + 1, bisect.bisect_left(nums, target - nums[end] - nums[index], index + 1, end) - 1)
            j = end
            value = nums[index]
            while i < j:
                sum = value + nums[i] + nums[j]
                if abs(sum - target) < abs(res - target): res = sum
                if sum > target: j -= 1
                elif sum < target: i += 1
                else:
                    return target
        return res