# Hashmap c++ solution, quadratic time, 72ms

• I assume all the solutions are like (x, y, z) and x <= y <= z, so no duplicate.

First scan the array into a map, so the keys are sorted.
Then outer loop the first element x, and inner loop the second y, and use map to find z.

``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result(0);
// scan the array into a map, record the occurrence
map<int, int> m;
for (int i = 0; i < nums.size(); ++i){
if (m.find(nums[i]) == m.end()) m[nums[i]] = 1;
else ++m[nums[i]];
}

typedef map<int, int>::iterator map_it;
// OUTER LOOP on x, start from the front
for (map_it iter = m.begin(); iter != m.end(); ++iter){
if (iter->first > 0) break;  // if the minimum is greater than 0, no more solutions
iter->second -= 1;           // keep track on the occurrence
// INNER LOOP on y, start from where x stays
for (map_it jter = iter; jter != m.end(); ++jter){
if (jter->second == 0) continue;         // no more to use, continue
int z = -(iter->first + jter->first);
jter->second -= 1;                       // keep track on the occurrence
// if we find the third elem, make sure it's max, and it's ok to use
map_it temp = m.find(z);
if (temp != m.end()){
if (z >= jter->first && temp->second != 0) {
result.push_back({iter->first, jter->first, z});
}
}
jter->second += 1;      // recover the occurrence
}
iter->second += 1;          // recover the occurrence
}
return result;
}
};``````

• so your time complexity is nlogn + (n^2)logn ?

• right..right..searching for the 3rd elem takes logn in a treemap, so n^2 * logn, not cool, not cool at all. Thanks man

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