# C++ solution O(n^2) using sort

• Sort the vector and then no need to run O(N^3) algorithm as each index has a direction to move.

The code starts from this formation.

``````----------------------------------------------------
^  ^                                               ^
|  |                                               |
|  +- second                                     third
+-first
``````

if nums[first] + nums[second] + nums[third] is smaller than the target, we know we have to increase the sum. so only choice is moving the second index forward.

``````----------------------------------------------------
^    ^                                             ^
|    |                                             |
|    +- second                                   third
+-first
``````

if the sum is bigger than the target, we know that we need to reduce the sum. so only choice is moving 'third' to backward. of course if the sum equals to target, we can immediately return the sum.

``````----------------------------------------------------
^    ^                                          ^
|    |                                          |
|    +- second                                third
+-first
``````

when second and third cross, the round is done so start next round by moving 'first' and resetting second and third.

``````----------------------------------------------------
^    ^                                           ^
|    |                                           |
|    +- second                                 third
+-first
``````

while doing this, collect the closest sum of each stage by calculating and comparing delta. Compare abs(target-newSum) and abs(target-closest). At the end of the process the three indexes will eventually be gathered at the end of the array.

``````----------------------------------------------------
^    ^    ^
|    |    `- third
|    +- second
+-first
``````

if no exactly matching sum has been found so far, the value in closest will be the answer.

``````int threeSumClosest(vector<int>& nums, int target) {
if(nums.size() < 3) return 0;
int closest = nums[0]+nums[1]+nums[2];
sort(nums.begin(), nums.end());
for(int first = 0 ; first < nums.size()-2 ; ++first) {
if(first > 0 && nums[first] == nums[first-1]) continue;
int second = first+1;
int third = nums.size()-1;
while(second < third) {
int curSum = nums[first]+nums[second]+nums[third];
if(curSum == target) return curSum;
if(abs(target-curSum)<abs(target-closest)) {
closest = curSum;
}
if(curSum > target) {
--third;
} else {
++second;
}
}
}
return closest;
}``````

• can you please explain a bit why complexity is O(n^2)? thanks

• Why do you use sort?

• because you need to loop on N elements N times average

• without sorting you will never know left element is always smaller than or the same to the right one so you have to compare everywhere again which means N^2 x N

• This post is deleted!

• why closest initialized as
int closest = v[0]+v[1]+ v[2];

• It's just initialized as the sum of any three numbers in the array. Because you will iterate all the combinations of three numbers in the array, if there is a combination whose sum is closer to the target, closest will be updated. Just make sure the initial value of closest is not closer than the possible closest result in the array.

• Can u explain line6
if(first > 0 && nums[first] == nums[first-1]) continue;
what does it mean?

• I believe it is used to jump over the duplicated combination

• here is my code which is just similar to the code for previous problem 3Sum . but here we don't need to take consideration of duplicates.

threeSumClosest

``````int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int n=nums.size(),ans;
int min=INT_MAX;
for(int i=0;i<n-2;i++){
int l=i+1, r= n-1;
while(l<r){
int sum =nums[i]+nums[l]+nums[r];
if(abs(sum-target)<min){  // updating the sum if sum  so far. is closest to target
min=abs(sum-target);
ans=sum;
}
if(sum<target) l++;        //
else if(sum>target)r--;
else {
ans=sum;  // we have sum equal to target which is closest so no need to check further
i=n-2;  // for breaking the outer for loop
break;  // for breaking current while loop
}
}
}
return ans;
}
``````

threeSum

``````vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n=nums.size();
vector<vector<int>> res;
for(int i=0;i<n-2;i++){
if(i>0 && (nums[i]==nums[i-1]) )continue;   // to avoid duplicates
int l=i+1, r= n-1;
while(l<r){
int sum =nums[i]+nums[l]+nums[r];

if(sum<0) l++;
else if(sum>0)r--;
else {
res.push_back(vector<int>{nums[i],nums[l],nums[r]});
while(l+1<r && nums[l]==nums[l+1])l++;    // to avoid duplicates
while(l<r-1 && nums[r]==nums[r-1]) r--;     // to avoid duplicates
l++; r--;
}
}
}

return res;
}``````

• C# implementation based on asbear's idea

``````    private int ThreeSumClosest(int[] nums, int target)
{
if (nums.Length <= 3)
{
return nums.Aggregate((a, b) => a + b);
}

Array.Sort(nums);

int n = nums.Length;
int ans = nums[0] + nums[1] + nums[2];

for (int i = 0; i < n - 2; i++)
{
int j = i + 1;
int k = n - 1;

while (j < k)
{
int sum = nums[i] + nums[j] + nums[k];
if (sum == target)
{
return sum;
}

if (Math.Abs(target - sum) < Math.Abs(target - ans))
{
ans = sum;
}

if (sum > target)
{
k--;
}
else
{
j++;
}
}
}

return ans;
}``````

``````int vsize = nums.size();
int firstThree = nums[0] + nums[1] + nums[2];
int lastThree = nums[vsize-1] + nums[vsize-2] + nums[vsize-3];

if((target-firstThree) < 0 && (target-lastThree) < 0) return firstThree;
if((target-firstThree) > 0 && (target-lastThree) > 0) return lastThree;
``````

at the top to make it faster, for a few specific cases.

• @timetraveler_0

``````if(target < firstThree) return firstThree;
if((target > lastThree) return lastThree;
``````

is enough.

by the way, in the first for loop, add

``````n = nums.size();
int with_i_fixed_max = nums[i]+nums[n-1]+nums[n-2] ;
if (with_i_fixed_max  < target && abs(with_i_fixed_max - target) < abs(target - closest) ) {
closest = with_i_fixed_max;
continue;
}
int with_i_fixed_min = nums[i]+nums[i+1]+nums[i+2]
if (with_i_fixed_min > target && abs(with_i_fixed_min - target) < abs(target - closest) ) {
closest = with_i_fixed_min;
continue;
}
``````

also helps for some special cases.

• This post is deleted!

• @ThreeRice Excpet the same number