16. 最接近的三数之和

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

示例：

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

提示：

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

思路--双指针法

首先判断如果数组为空，或者数字长度小于3，则直接返回0。
接着对数组进行排序。
遍历数组：
从第二个元素开始，如果当前的数字和前一个数字相同，那么对于重复元素：直接跳过本次循环，避免出现重复解
令左low = i + 1， high = length - 1，当low < high，执行循环：
 计算三个数的和：s = nums[i] + nums[low] + nums[high]
若s == target:则直接返回target
若s ！= target，根据abs(s - target) 与abs(ans - target)大小，更新ans的值
并且，若 s > target，说明总和太大，high左移
若s <  target，说明总和太小，low 右移
并且判断左界和右界是否和下一位置重复，去除重复解，并同时将 low，high移到下一位置，寻找新的解

python3解法--双指针法

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        length = len(nums)
        if not nums or length < 3: return 0
        ans = 10 ** 7
        nums.sort()
        for i in range(length):
            if i > 0 and nums[i] == nums[i - 1]: continue
            low = i + 1
            high = length - 1
            while low < high:
                s = nums[i] + nums[low] + nums[high]
                if s == target:
                    return target
                if abs(s - target) < abs(ans - target):
                    ans = s
                if s > target:
                    while low < high and nums[high] == nums[high - 1]:
                        high -= 1
                    high -= 1
                else:
                    while low < high and nums[low] == nums[low + 1]:
                        low += 1
                    low += 1
        return ans

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