16-最接近的三数之和

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

---

示例

输入：nums = [-1，2，1，-4],  target = 1
输出：2
解释：与target最接近的三个数的和为2. (-1 + 2 + 1 = 2).

---

解法

核心思想：采用双指针，

若target-sum>0，说明sum太小，low向高移动
若target-sum<0，说明sum太大，high向低移动

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 只有三个数字，直接相加返回
        if len(nums) == 3:
            return sum(nums)
        # 对nums进行排序
        nums.sort()
        # 初始差值为最大值
        d_value = sys.maxsize
        for i in range(len(nums)):
            # low=i+1为去除之前判断过得操作
            low, high = i+1, len(nums)-1
            while(low < high):
                x = target - nums[low] - nums[high] - nums[i]
                # 进行差值
                if abs(x) < abs(d_value):
                    d_value = x
                if x > 0:
                    low += 1
                elif x < 0:
                    high -= 1
                elif x == 0:
                    return target
        return target - d_value

---

来源

LeetCode中该题地址，Click here!