Solution in O(n^2*log(n)), using binary search


#1
int Solution::threeSumClosest(vector<int> &A, int B) {
    int ans = 0, min_diff=INT_MAX, n = A.size();
    if (n == 3) return A[0] + A[1] + A[2];
    sort(A.begin(), A.end());
    int i, j, k, val, s;
    for(i = 0; i < n-2; i++){
        for(j = i+1; j < n-1; j++){
            s = A[i] + A[j];
            k = lower_bound(A.begin()+j, A.end(), B-s) - A.begin();
            if (k <= j || k == j+1) k = j+1;
            else if (k == n) k = n-1;
            else {
                if (abs(B - (s + A[k-1])) < abs(B - (s + A[k])))
                    k--;
            }
            val = s + A[k];
            if (abs(B - val) < min_diff){
                min_diff = abs(B-val);
                ans = val;
            }
        }
    }
    return ans;
}