[LeetCode] 16. 最接近的三数之和

[Animenzzzz]

题目描述：

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解题思路：这题和 三数之和、四数之和的思路一样。都是先定位第一个数，然后后两个数用left，right两个指针来定位。如果遇到了更接近的，就更新之和和最小绝对值。如果和小于target，则left加1；否则，right减1

C++解题：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int res = nums[0]+nums[1]+nums[2],abs_min = abs(res - target);
        for (int i = 0; i < nums.size() - 2; i++)
        {
            if(i && nums[i] == nums[i-1]) continue;
            int left = i+1,right = nums.size() -1;
            while (left < right)
            {
                int res_tmp = nums[i]+nums[left]+nums[right];
                int abs_tmp = abs(res_tmp - target);
                if(abs_min > abs_tmp){
                    abs_min = abs_tmp;
                    res = res_tmp;
                }
                if(res_tmp < target) left++;
                else right--;
            }
        }
        return res;
    }
};