# C++ O(N^2) solution, only 8ms.

• ``````class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());

int n = nums.size();
int closest_sum = nums[n-3] + nums[n-2] + nums[n-1];

if (closest_sum <= target) {
return closest_sum;
}

int min_diff = closest_sum - target;

for (int i = 0, j, k; i < n-3; i++) {
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}

int minsum = nums[i] + nums[i+1] + nums[i+2];
int diff1 = minsum - target;
if (diff1 >= 0) {
if (diff1 < min_diff) {
closest_sum = minsum;
}
break;
}

int maxsum = nums[i] + nums[n-2] + nums[n-1];
int diff2 = target - maxsum;
if (diff2 >= 0) {
if (diff2 < min_diff) {
closest_sum = maxsum;
min_diff = diff2;
}
continue;
}

j = i + 1, k = n - 1;
while (j < k) {
if (nums[j] == nums[j-1]) {
j++;
} else if (nums[k] == nums[k+1]) {
k--;
} else {
int sum = nums[i] + nums[j] + nums[k];
int diff = sum - target;
if (diff < 0) {
j++;
diff = -diff;
} else if (diff > 0) {
k--;
} else {
return sum;
}
if (diff < min_diff) {
min_diff = diff;
closest_sum = sum;
}
}
}
}
return closest_sum;
}
};``````

• can you tell us what is the critical idea in your code to reduce the run time from 16ms to 8ms?

• This is a wrong answer when you try this as input, although it is accepted.

``````[1,1,1,4,7,9]
6``````

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