3Sum Closest

Analysis:

1. Sort the vector;

2. Set i, j, k and traverse;

3. Start from i, j is after i, and k is the last element;

4. If the

Trick: By increasing j and decreasing k, to reduce the complexity from n^3 to n^2.

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        sort(num.begin(),num.end());
        int n = num.size();
        int closest = num[0]+num[1]+num.back();
        int sum;
        for(int i=0;i<n-2;++i)
        {
            int j=i+1;
            int k=n-1;
            while(j<k)
            {
                sum = num[i]+num[j]+num[k];
                if(abs(sum-target)<abs(closest-target))  
                    closest=sum;
                if(sum==target)                     
                    return target;
                if(sum<target)
                    j++;
                else
                    k--;
            }
        }
        return closest;
    }
    
};