原题网址：

描述

给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，返回这三个数的和。

只需要返回三元组之和，无需返回三元组本身

您在真实的面试中是否遇到过这个题？  是

样例

例如 S = [-1, 2, 1, -4] and target = 1. 和最接近 1 的三元组是 -1 + 2 + 1 = 2.

挑战

O(n^2) 时间, O(1) 额外空间。

标签

排序

两根指针

数组

 

思路：与57题三数之和方法类似，只不过不需要去重复（当然去除也可以），而且要多定义一个差值，target与数组中三数之和的差值，遍历找到差值绝对值最小时的三数之和。

 

AC代码：

class Solution {public:    /**     * @param numbers: Give an array numbers of n integer     * @param target: An integer     * @return: return the sum of the three integers, the sum closest target.     */    int threeSumClosest(vector
            
              &numbers, int target) {        // write your code here        int result=0;    int diff=INT_MAX;//初始差值可以定义为int型最大值，也可以定义为num[0]+num[1]+num[2]，要保证数组元素能够覆盖初值;    int n=numbers.size();    sort(numbers.begin(),numbers.end());    for (int i=0;i
             
              target)            {                k--;            }            else            {                j++;            }            if (abs(target-sum)
             
            

 

可以参考：