leetcode题解16：最接近的三数之和

描述

该题来自于力扣第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

分析

首先想到三数之和的解法，将数组排序，然后先固定第一个数，接下来就是如何找到另外两个数，使得三个数的和最接近target。还是用双指针法，假设第一个数下标为first，第二个数下标为second=first+1，第三个数下标为third=n-1，记s=nums[first]+nums[second]+nums[third]，由于数组是排过序的，所以分三种情况

如果s=target，直接返回这target就可以了；
如果s>target，那么移动指针second，只会让s更大，从而与target相差更大，所以让third--；
如果s<target，那么移动指针third，只会让s更小，从而与target相差更大，所以让second--

经过上述步骤，如果没有返回，记录s-target的绝对值是否是最小的，并更新s，然后遍历first就可以找到最终结果了。

算法

排序数组
将最接近target的值closest初始化为nums[0]+nums[1]+nums[2]
第一个数下标first从0到n-3遍历数组
进入循环体，设second=first + 1，third=n-1，计算s=nums[first] + nums[second] + nums[third]
判断s与target的关系，如果s==target，直接返回target，退出程序；否则按照上面的分析更新second，third
如果|s-target|<|closest-target|，那么更新closest=s
判断second是否大于等于third，如果是，退出循环；否则first++，并进入循环体（第4步）

小优化：

在三数之和中，为了避免找到重复解，每到一个新数时可以和前面数比较，如果一样直接跳过。这里在遍历first,second,third三个数时都可以跳过重复值，避免重复计算。

代码

python3

class Solution:
    def threeSumClosest(self, nums, target):
        nums.sort()
        closest = sum(nums[:3])
        first = 0
        while first < len(nums) - 2:
            second, third = first + 1, len(nums) - 1
            while second < third:
                s = nums[first] + nums[second] + nums[third]
                if abs(s - target) <= abs(closest - target):
                    closest = s
                    if closest == target:
                        return target
                if s > target:
                    while third > second and nums[third] == nums[third-1]:
                        third -= 1
                    third -= 1
                elif s < target:
                    while second < third and nums[second] == nums[second+1]:
                        second += 1
                    second += 1

            while first < len(nums) - 2 and nums[first] == nums[first+1]:
                first += 1
            first += 1

        return closest

c++

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int first = 0;
        int closest = nums[0] + nums[1] + nums[2];
        while (first < nums.size() - 2) {
            int second = first + 1;
            int third = nums.size() - 1;
            while (second < third) {
                int s = nums[first] + nums[second] + nums[third];
                if (abs(s - target) <= abs(closest - target)) {
                    closest = s;
                    if (closest == target) return target;
                }
                if (s > target) {
                    while((third > second) && (nums[third] == nums[third-1])) third--;
                    third--;
                }
                else if(s < target) {
                    while ((second < third) && (nums[second] == nums[second + 1])) second++;;
                    second++;
                }
            }
            while ((first < nums.size() - 2) && (nums[first + 1] == nums[first])) first++;
            first++;
        }
        return closest;
    }
};

java

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int first = 0;
        int closest = nums[0] + nums[1] + nums[2];
        while (first < nums.length - 2){
            int second = first + 1;
            int third = nums.length - 1;
            while (second < third){
                int s = nums[first] + nums[second] + nums[third];
                if (Math.abs(s - target) <= Math.abs(closest - target)){
                    closest = s;
                }
                if (closest == target) return target;
                if (s > target){
                    while ((third > second) && (nums[third] == nums[third-1])) third--;
                    third--;
                }
                else if (s < target){
                    while ((second < third) && (nums[second] == nums[second+1])) second++;
                    second++;
                }
            }
            while ((first < nums.length - 2) && (nums[first] == nums[first+1])) first++;
            first++;
        }
        return closest;
    }
}