16.最接近的三数之和

https://leetcode-cn.com/problems/3sum-closest/

难度：中等

题目：

给定一个包括n 个整数的数组nums和 一个目标值target。找出nums中的三个整数，

使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。

提示：

• 3 <= nums.length <= 10^3
• -10^3 <= nums[i] <= 10^3
• -10^4 <= target <= 10^4

示例：

示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

分析

这道题的题目比较短，获取最接近target目标值的三数之和。

首先拿到这种题，我们要先看下提示中的取值范围，3 <= nums.length <= 10^3条件标志着。

不会出现不足三个数字的异常场景，但10^3 如果三层for循环10^9必然会超时，暴力解法不通。

那么，下来就需要考虑优化方案：

1. 二分查找 or hash表？

• 二分查找和hash表只针对单个数字，那势必我们需要先双层循环再二分，10^6一样会超时。

2. 缩减条件

• 既然三个数字我们有些无从下手，那么先使用一层for循环，减少一个数字的筛选再来考虑是否就简单了一些。
• 减少一个数字后，我们的题目变成了查找数组中某两个最接近target - num1，是不就变成了一道基础题。

3. 实现方案

• 我们先将nums排序
• 设置返回值ret，初始为float('inf')无穷大
• 开始for i in range(len(nums))循环
• 设置left = i + 1,right = length - 1
• tmp = nums[left] + nums[rigth]
• 比较 ret和tmp+nums[i]，哪个更接近target，并赋值给ret
• 如果tmp = target - nums[i],表示找到了三个数等于target直接返回target
• 如果tmp > target - nums[i],我们将right -= 1
• 如果tmp < target - nums[i],我们将left -= 1
  最终，即可获取结果。

解题：

class Solution:
    def threeSumClosest(self, nums, target):
        ret = float('inf')
        nums.sort()
        length = len(nums)
        for i in range(length - 2):
            left = i + 1
            right = length - 1
            while left < right:
                tmp = nums[i] + nums[left] + nums[right]
                ret = tmp if abs(tmp - target) < abs(ret - target) else ret
                if tmp == target:
                    return target
                if tmp > target:
                    right -= 1
                else:
                    left += 1
        return ret