Leetcode16 3Sum Cloest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

题目意思是给一个数组和一个target，从数组中找到三数之和，且该和要与target差距最小。
刚开始思路是设置三个指针: i,j,k同步移动：i=0;j=i+1;k=j+1,这样可以把时间复杂度降低到O(n2)，但是这样做会漏掉一些组合，比如 (-1,1,-4)就不会被涉及到，测试未通过。

之后考虑这种解法：排序+双指针的思路。
考虑这个数组
[1,2,4,8,16,32,64,128]，target=82
可以先对整个数组排个序，之后确定一个值和2个指针left和right，right在最右边；当确定一组left和right后，得出三元素的和，并于target计算距离,当和小于target时，自然左指针后移，当和大于target时，右指针前移，这样既可以保证时间控制在O(n2)，又可以保证遍历到所有可能的元素。

/**
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
*/

#include <vector>
#include <cstdlib>
#include<iostream>

using namespace std;

int partition(vector<int> &v, int low,int high){
    int pivot = v[low];
    while(low<high){
        while((low<high) && (v[high]>=pivot))
            high--;
        v[low] = v[high];

        while((low<high) && (v[low]<=pivot))
            low++;
        v[high] = v[low];
    }v[low] = pivot;

    return low;
}

void sotter(vector<int> &v, int low,int high){
    if(low<high){
        int pi = partition(v,low,high);
        sotter(v,low,pi-1);
        sotter(v,pi+1,high);
    }
}


class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int distance=99999;
        int tmp_distance;
        int sum = 0;
        if(nums.size()<3)
            return 0;

        sotter(nums,0,nums.size()-1);
        //for(auto item:nums)
         //   cout<<item<<" ";

        for(int i=0;i<nums.size()-2; i++){
            int left = i+1;
            int right = nums.size()-1;
            while(left<right){
                int tmp = nums[i]+nums[left]+nums[right];
                tmp_distance = abs(target - tmp);
                if(tmp_distance<distance){
                    distance = tmp_distance;
                    sum = tmp;
                }
                if(tmp<target) left++;
                else right--;
            }
        }

        return sum;
    }
};



int main(int argc, char const *argv[])
{
    Solution solu;
    vector<int> v = {-1, 2, 1, -4};
    cout<<solu.threeSumClosest(v,1)<<endl;
    return 0;
}