# Share my AC C++ solution, around 50ms, O(N*N), with explanation and comments

• the key idea is the same as the `TwoSum` problem. When we fix the `1st` number, the `2nd` and `3rd` number can be found following the same reasoning as `TwoSum`.

The only difference is that, the `TwoSum` problem of LEETCODE has a unique solution. However, in `ThreeSum`, we have multiple duplicate solutions that can be found. Most of the OLE errors happened here because you could've ended up with a solution with so many duplicates.

The naive solution for the duplicates will be using the STL methods like below :

``````std::sort(res.begin(), res.end());
res.erase(unique(res.begin(), res.end()), res.end());
``````

But according to my submissions, this way will cause you double your time consuming almostly.

A better approach is that, to jump over the number which has been scanned, no matter it is part of some solution or not.

If the three numbers formed a solution, we can safely ignore all the duplicates of them.

We can do this to all the three numbers such that we can remove the duplicates.

Here's my AC C++ Code:

``````vector<vector<int> > threeSum(vector<int> &num) {

vector<vector<int> > res;

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

for (int i = 0; i < num.size(); i++) {

int target = -num[i];
int front = i + 1;
int back = num.size() - 1;

while (front < back) {

int sum = num[front] + num[back];

// Finding answer which start from number num[i]
if (sum < target)
front++;

else if (sum > target)
back--;

else {
vector<int> triplet(3, 0);
triplet[0] = num[i];
triplet[1] = num[front];
triplet[2] = num[back];
res.push_back(triplet);

// Processing duplicates of Number 2
// Rolling the front pointer to the next different number forwards
while (front < back && num[front] == triplet[1]) front++;

// Processing duplicates of Number 3
// Rolling the back pointer to the next different number backwards
while (front < back && num[back] == triplet[2]) rear--;
}

}

// Processing duplicates of Number 1
while (i + 1 < num.size() && num[i + 1] == num[i])
i++;

}

return res;

}``````

• This post is deleted!

• You should change `rear` to `back`

• Thank you for your comment. The `rear` word just came out of my mind before `back` at that time, and they have almost the same meaning. But anyway, thank you for pointing that out.

• Very clear solution! Thanks for sharing.

• I had made it more faster by adding this piece of code to pruning your algorithm.

``````        if(target < 0)
{
break;
}
``````

^_^

``````vector<vector<int> > threeSum(vector<int> &num) {

vector<vector<int> > res;

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

for (int i = 0; i < num.size(); i++) {

int target = -num[i];
int front = i + 1;
int back = num.size() - 1;

if(target < 0)
{
break;
}

while (front < back) {

int sum = num[front] + num[back];

// Finding answer which start from number num[i]
if (sum < target)
front++;

else if (sum > target)
back--;

else {
vector<int> triplet(3, 0);
triplet[0] = num[i];
triplet[1] = num[front];
triplet[2] = num[back];
res.push_back(triplet);

// Processing duplicates of Number 2
// Rolling the front pointer to the next different number forwards
while (front < back && num[front] == triplet[1]) front++;

// Processing duplicates of Number 3
// Rolling the back pointer to the next different number backwards
while (front < back && num[back] == triplet[2]) back--;
}

}

// Processing duplicates of Number 1
while (i + 1 < num.size() && num[i + 1] == num[i])
i++;

}

return res;

}``````

• I wonder why should'nt I put the removing duplicates of rear and front after the closed } of the else condition? why it should be inside else ? can you tell me why it is incorrect to put it after else?

• If we remove duplicates (as you mentioned in your "naive solution"), we will miss solution sets which include duplicates like {-2,-2,4}. Isn't it?
Correct me if I am missing something.

• feels like we only need one of processing duplicates for Number 2 and 3. Since the value of num[i] is unchanged, it is ensured that,for the next solution, num[front](or num[back) will have different value if num[back](or num[front]) becomes different.

• Great! This is my solution based on yours with shorter code. Running a bit more faster:

``````vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;

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

for (auto i = 0; i < nums.size();) {
auto target = -nums[i];
int l = i + 1, u = nums.size() - 1;

while (l < u) {
auto sum = nums[l] + nums[u];

if (sum < target)
while (nums[++l] == nums[l - 1]);  // Processing duplicates of Number 2
else if (sum > target)
while (nums[--u] == nums[u + 1]);  // Processing duplicates of Number 3
else {
result.push_back(vector<int>{nums[i], nums[l], nums[u]});
while (nums[++l] == nums[l - 1]);  // Processing duplicates of Number 2
while (nums[--u] == nums[u + 1]);  // Processing duplicates of Number 3
}

}

// Processing duplicates of Number 1
while (nums[++i] == nums[i - 1]);
}

return result;
}``````

• you can also cut "num[back] < 0" search progress

• I don't understand -- why is target < 0 not a valid condition?

Nevermind -- figured it out. If nums[i] is positive, there is no way for two larger numbers (due to sorting) to sum to this value.

• If changing "i < num.size()" in the first line of the FOR loop to "i < num.size()-2", the function will be wrong. Could you please tell me why this will happen? Thank you!

• For example,a sorted array a<b<c, the aim is -1a=b+c
if the target -1
a<0, then a>0. so b+c<0. But 0<a<b<c, so b+c<0 is impossible.

• Because num.size() is unsigned integer type. If your input is [ ], num.size()-2 is a very large number (18446744073709551614), you will get runtime error at the FOR loop.

• here is my code based on your algorithm with some optimization .

``````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;
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++;
while(l<r-1 && nums[r]==nums[r-1]) r--;
l++; r--;
}
}
}

return res;
}``````

• @SGM nums.size() is unsigned long, and unsigned(0)-2 is not -2, you should replace nums.size()-2 with static_cast<int>(nums.size())-2

• As someone brand new to Leetcode, I don't get the O(N x N) complexity of this Solution. Is that because you disregard the complexity of Sorting?. As much I understand, the complexity should be O(N x N) for the two loops plus that of Sorting. Thank you.
@kun3

• @abbasfaisal O(N^2) > O(NlgN) and hence O(N^2 + NlgN) is simplified to O(N^2)

• @wfxr When the input is [0,0,0,0], you code will throws an exception caused by vector subscript out of range. LeetCode OJ will not throws this exception but Visual Studio 2017 will. This is my code based on your code can avoid this exception.

``````std::vector<std::vector<int>> threeSum(std::vector<int>& nums)
{
std::vector<std::vector<int>> result;

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

for (auto i = 0; i < nums.size() - 2;)
{
auto target = -nums[i];
int l = i + 1, u = nums.size() - 1;

while (l < u)
{
auto sum = nums[l] + nums[u];

if (sum < target)
while (++l < nums.size() && nums[l] == nums[l - 1]); // Add a judgement condition of the range of vector subscript
else if (sum > target)
while (--u < nums.size() && nums[u] == nums[u + 1]); // Add a judgement condition of the range of vector subscript
else
{
result.push_back(std::vector<int>{nums[i], nums[l], nums[u]});
while (++l < nums.size() && nums[l] == nums[l - 1]); // Add a judgement condition of the range of vector subscript
while (--u < nums.size() && nums[u] == nums[u + 1]); // Add a judgement condition of the range of vector subscript
}
}

// Add a judgement condition of the range of vector subscript
while (++i < nums.size() && nums[i] == nums[i - 1]);
}

return result;
}
``````

#### Some of my advice

First, I think the for loop can be break when `i = nums.size() - 2`. Because , if `i >= nums.size() - 2`, the remaining amount of data is less than three. The remaining data can not constitute a complete triple. So we can break the loop when `i < nums.size() - 2`.

Second, I think if `target < 0`, you can also break the `for` loop. Because if `target < 0` means `nums[i] > 0`, so the number after this also greater than 0 (nums are sorted in ascending order). The sum of three positive numbers can not be equal to zero. So we can break the `for` loop when `target < 0`.

This is the modified `for loop` code snippet.

``````    int target{};
// Modify the entry conditions of this loop
for (auto i = 0; i < nums.size() - 2 && (target = -nums[i]) >= 0;)
{
int l = i + 1, u = nums.size() - 1;

while (l < u)
{
auto sum = nums[l] + nums[u];
....
``````

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