16.最接近的三数之和

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

这道题比上一题简单，因为不需要剔重。
仍然使用双指针法，逐步向中间靠拢，维护一个dis，每次找到最小的差值绝对值
O(n^2)的方法

具体代码：

#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

int threeSumClosest(vector<int>& nums, int target) {
    int dis = INT_MAX;
    int res = 0;
    if(nums.size() < 3){
        return res;
    }
    
    sort(nums.begin(), nums.end());
    
    for(int i = 0; i < nums.size() - 2; i++){
        int tar = target - nums[i];
        int left = i + 1;
        int right = nums.size() - 1;
        while(left < right){
            if(nums[left] + nums[right] == tar){
                return target;
            }
            else if(nums[left] + nums[right] < tar){
                if(dis > tar - nums[left] - nums[right]){
                    dis = tar - nums[left] - nums[right];
                    res = target - dis;
                }
                left++;
            }
            else{
                if(dis > nums[left] + nums[right] - tar){
                    dis = nums[left] + nums[right] - tar;
                    res = target + dis;
                }
                right--;
            }
        }
    }
    
    return res;
}

int main(){
    int a[10] = {-1,2,1,-4};
    vector<int> nums(a, a+4);
    cout << threeSumClosest(nums, 1);
    return 0;
}