16. 最接近的三数之和 - 力扣

1. 题目

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

2. 示例

3.分析

做这道题目前，先做这道：三数之和 ，对应题解：三数之和(排序+单调性+双指针)

这道题目跟三数之和一样，都是利用 排序+单调性+双指针。

整体思想就是：固定一个数，在这个数的区间内寻找 两个值，+固定数 的和，若区间内存在更优的两个数与固定数的和更接近 target，则更新 三数和。

通过什么条件更新？

利用 当前三数和减去target 的绝对值 跟 上个三数和减去target 的绝对值 进行比较，若小于上个则更新。因为绝对值越小说明越三数和越接近 target。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int close = nums[0] + nums[1] + nums[2];
 
        for(int i = 0; i < n-2; i++)
        {
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int left = i+1, right = n-1;
            while(left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];
                // 更新close
                if(abs(sum-target) < abs(close-target)) close = sum;
 
                if(sum > target) right--;
                else if(sum < target) left++;
                else return target; // 若等于target则直接返回target
            }
        }
        return close;   
    }
};