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

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/3s…

分析

要求三数之和和目标值最接近，就是求a+b+c-t越接近0的a,b,c之和。

1. 题目与15.三数之和类似，完全可以根据三数之和的思路做一些修改求出。
2. 三数之和是求a+b+c=0的组合，这里是求a+b+c更接近target的和，我们按照三数之和中的遍历数组的方法对数组进行遍历，然后在循环体内部判断当前三数之和是否更接近target，如果更接近，那么就把该和保存起来，继续遍历。

例：nums = {-1,2,1,-4}

1. 先对数组进行排序
2. 对数组进行循环获取a
3. 双指针left,right分别指向a+1和numsSize-1
4. 判断当前三数之和与target的差值的绝对值是否比前几次循环求得的三数之和与target的差值的绝对值小(差值的绝对值越小，就表示越接近target)
5. 当a+b+c>target时，说明b+c略大了，由于数组已排序，因此right指针往左移
6. 当a+b+c<target时，说明b+c略小了，因此left指针往右移
7. 当a+b+c=target时，结果就是a+b+c之和，直接返回即可
8. 返回数组差值更接近0的三数之和即可

实现

int compare(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int threeSumClosest(int* nums, int numsSize, int target)
{
    if (numsSize < 3) {
        return NULL;
    }
    qsort(nums, numsSize, sizeof(nums[0]), compare);
    int sum = nums[0] + nums[1] + nums[numsSize-1];  // 当前最接近target的三数之和，差值的绝对值越小，则与target越接近
    for (int i = 0; i < numsSize; i++) {
        int left = i + 1;
        int right = numsSize - 1;
        while (left < right) {
            int tmpSum = nums[i] + nums[left] + nums[right];
            if (abs(tmpSum - target) < abs(sum - target)) {
                sum = tmpSum;
            }
            if (tmpSum > target) {
                right--;
            } else if (tmpSum < target) {
                left++;
            } else {
                return sum;
            }
        }
    }
    return sum;
}
复制代码