题目描述

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

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

解题思路

该题与前面的第15题类似，同样也是在排序后，固定第一个元素的值，然后使用双指针遍历得到当前的循环的最佳结果。借助双指针，我们就可以对枚举的过程进行优化。
如果 $a+b+c \geq \textit{target}$ ，那么就将 $p_c$ 向左移动一个位置；
如果 $a+b+c \leq \textit{target}$ ，那么就将 $p_b$ 向左移动一个位置；

    int threeSumClosest(vector<int>& nums, int target) {
        if (nums.size() < 3)
            throw runtime_error("must be bigger than 3");

        sort(nums.begin(), nums.end());
        int ret = nums[0] + nums[1] + nums[2];

        for(int i=0;i<nums.size()-2;i++){
            int l=i+1;
            int r=nums.size()-1;

            while(l<r){
                int cur_sum = nums[i]+nums[l]+nums[r];
                ret = abs(cur_sum-target) < abs(ret-target) ? cur_sum : ret;
                if(cur_sum==target){
                    return target;
                }else if(cur_sum>target){
                    r--;
                }else{
                    l++;
                }
            }
        }

        return ret;
    }