# 21 lines, 56 ms in C++

• ``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
if(nums.size() < 3) return ans;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() - 2; i ++) {
// in case of duplicate solutions
if(i > 0 && nums[i] == nums[i-1]) continue;
int a = nums[i];
int lf = i + 1;
int rt = nums.size() - 1;
while(lf < rt) {
int b = nums[lf];
int c = nums[rt];
if(0 == a + b + c) {
ans.push_back(vector<int> {a, b, c});
// in case of duplicate solutions
while(lf < nums.size() && nums[lf] == b) lf ++;
// in case of duplicate solutions
while(rt >= 0 && nums[rt] == c) rt --;
}
else if(a + b + c > 0) rt --;
else lf ++;
}
}
return ans;
}
};``````

• @johnsondu Thank you so much, I couldn't think of any n^2 solution, the ones used with mutlimaps failed because time limit exceeded though the answers were right.Can you please elaborate on why this solution works ? especially the last two conditions

``````else if(a + b + c > 0) rt --;
else lf ++;
``````

from what i understood I think that if the final sum > 0 we need to move backwards in order to get a lesser number to make the final sum as 0 and the reverse if sum<0. Correct me if I am wrong.

Here is my code using multimaps, please let me kow if you can make any optimizations on this.

``````class Solution {
public:

vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
set<vector<int>> s;
multimap<int, int> dict;
for (auto i = 0; i<nums.size(); i++) {
dict.insert(std::pair<int, int>(nums[i], i));
}

vector<int> res;
vector<vector<int>> result;

for (int i = 0; i < nums.size(); i++) {
if (i>0 && nums[i] == nums[i - 1])
continue;
int sum = -nums[i];
for (int j = i + 1; j < nums.size(); j++) {
int x = sum - nums[j];
if (x<nums[0] || x>nums[nums.size() - 1])
continue;

if (dict.find(x) != dict.end() && dict.find(x)->second != j && dict.find(x)->second != i)
{
res = { -sum,nums[j],x };
sort(res.begin(), res.end());
if (s.find(res) == s.end()) {
result.push_back(res);
s.insert(res);
}
res.clear();
}

}
}
return result;
}
};
``````

• @sujiths52 just like you say, when a + b + c > 0, since a < b < c, then what we do in this case is deduce c, since a is fixed and b is smallest, and reverse is sum < 0. your code time complexity is O(n^2 logn), since find in map time complexity is O(log n), I suggest to you that may be use unordered_map<int, vector<int>> to store the original data information, where vector<int> store the int's subscripts. then complexity will be O(n^2)

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