16、最接近的三数之和-526互联

//最接近的三数之和
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

//双指针
int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end()); //排序

    int ans = nums[0] + nums[1] + nums[2];
    for(int i = 0; i<nums.size(); i++){
        int start = i+1, end = nums.size()-1;
        while(start<end){
            int sum = nums[i] + nums[start] + nums[end];
            if (abs(target-sum)<abs(target-ans))
            {
                ans = sum;
            }
            if (sum<target)
            {
                start++;
                /* code */
            }else if (sum>target)
            {
                end--;
                /* code */
            }else{
                return ans;
            }  
        }
    }

    return ans;
}

int main()
{
    vector<int> nums;
    nums.push_back(-4);
    nums.push_back(0);
    nums.push_back(5);
    nums.push_back(-5);
    nums.push_back(3);
    nums.push_back(3);
    nums.push_back(0);
    nums.push_back(-4);
    nums.push_back(-5);
    int result = threeSumClosest(nums, 3);
    cout<<result<<endl;
    return 0;
}

算法思想：

首先进行排序，使用C++的sort函数（第一个参数是迭代器的起始位置nums.begin()，第二个参数是迭代器的结束位置nums.end()）
然后遍历每一个数组nums[i],在这一层循环中，再设置一层循环计算sum = nums[i]+nums[start]+nums[end];
如果sum和tartget的距离更近，就更新ans
如果sum<target，增大start使得sum变大，则sum和target的距离可能会进一步缩小
如果sum>target，减小end使得sum变小，则sum和target的距离可能会进一步缩小
如果sum=target，则距离为0，直接返回sum

之和