# C++ solution with O(nlogn) time complexity

• A group of data proved this algorithm is NOT correct. Sorry for that. But is there a O(n logn) algorithm, please?

step 1: a quick sort.
step 2: set two indices start and end which locates at the beginning and the end of the num array.
use binary search to find the newTarget = target - num[start] - num[end] with index of p, if found, return the target directly, else record the minimal difference between the num[start]+num[p]+num[end] and target.
The loop ends when start >= end - 1

From the start to the end, n loops exists.
Each time log(n) for binary search, so the total cost is nlogn.

``````class Solution {
int findTarget(vector<int> &num, int start, int end, int target) {
if (start==end) {
return start;
}
if (end-start==1) {
return abs(num[end]-target) > abs(num[start]-target) ? start : end;
}
int mid = (start+end)/2;
if (num[mid]==target)
return mid;
else if(num[mid]>target)
return findTarget(num, start, mid, target);
else
return findTarget(num, mid, end, target);
}
public:
int threeSumClosest(vector<int> &num, int target) {
if (num.size()==0) return 0;
if (num.size()==1) return num[0];
if (num.size()==2) return num[0]+num[1];
if (num.size()==3) return num[0]+num[1]+num[2];

sort(num.begin(), num.end());

int start = 0;
int end = int(num.size()-1);

int mindiff = INT_MAX;
while (start<end-1) {

int newTarget = target - (num[start] + num[end]);
int p = findTarget(num, start+1, end-1, newTarget);
int curSum = num[start] + num[end] + num[p];
if (curSum == target) {
return target;
} else if(curSum > target) {
mindiff = abs(mindiff)>abs(target-curSum) ? target-curSum : mindiff;
end--;
} else {
mindiff = abs(mindiff)>abs(target-curSum) ? target-curSum : mindiff;
start++;
}
}

return target-mindiff;
}
};``````

• what if 1 3 11 14 21 30? for target as 36

• in the test above it is proved incorrect
[1 3 11 14 21 30] 36

• the closest three numbers are 1,14,21,not 3,11,21

• Yes, I am wrong. I am so sorry for that. But is there a correct O(n logn) method?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.