My own C++ solution,beat 88%

• ``````class Solution {
public:
vector< vector<int> > threeSum(vector<int>& nums) {
vector< vector<int> > ret;
sort(nums.begin(), nums.end());
int zeroIndex = lower_bound(nums.begin(), nums.end(), 0) - nums.begin();
vector<int> left(nums.begin(), nums.begin() + zeroIndex);
vector<int> right(nums.begin() + zeroIndex, nums.end());
if (right.size() >= 3 && right[0] ==0 && right[1] ==0 && right[2] == 0) {
vector<int> tmp(3, 0);
ret.push_back(tmp);
}
//left go first
for (int i = 0; i < left.size(); i++) {
if (i != 0 && left[i] == left[i - 1]) continue;
int index = upper_bound(right.begin(), right.end(), -left[i]) - right.begin() - 1;
int j = 0;
while (j < index) {
if ((right[j] + right[index]) == -left[i]) {
vector<int> tmp;
tmp.push_back(left[i]);
tmp.push_back(right[j]);
tmp.push_back(right[index]);
ret.push_back(tmp);
j++;
index--;
while(right[j]==right[j-1]) j++;
while(right[index]==right[index+1]) index--;
}
else if ((right[j] + right[index]) > -left[i]) {
index--;
}
else if ((right[j] + right[index]) < -left[i]) {
j++;
}
}
}

//right go second
for (int i = 0; i < right.size(); i++) {
if (i != 0 && right[i] == right[i - 1]) continue;
int index = upper_bound(left.begin(), left.end(), -right[i]) - left.begin();
int j = left.size() - 1;
while (index < j) {
if ((left[j] + left[index]) == -right[i]) {
vector<int> tmp;
tmp.push_back(right[i]);
tmp.push_back(left[j]);
tmp.push_back(left[index]);
ret.push_back(tmp);
j--;
index++;
while(left[j]==left[j+1]) j--;
while(left[index-1]==left[index]) index++;
}
else if ((left[j] + left[index]) < -right[i]) {
index++;
}
else if ((left[j] + left[index]) > -right[i]) {
j--;
}
}
}

return ret;
}
};
``````

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