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;
}
};
```