I first came up the O(N^2) solution with HashMap from 2Sum question as below.

Got TLE result occasionally and found other people have similar issue in discussion.

And most voted solution is also O(N^2).

Figured out the tricky part is at this line: if (numPos[numK] > j)

Even though numPos[numK] is an O(1) operation in theory, but it contains 2 operations if numK is not in numPos:

- lookup numK in numPos, O(1)
- insert numK in numPos with default value 0, O(1)

Insert operation may cause hash map rehash, which is a big penalty in time.

So the fix is also easy, run time dropped from 800ms down to 270ms, close to most voted solution 120ms in my submission.

auto iter = numPos.find(numK);

if (iter == numPos.end())

continue;

if (iter->second > j)

...

```
vector<vector<int>> threeSum1(vector<int>& nums) {
unordered_map<int, int> numPos;
numPos.reserve(10 * nums.size());
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
numPos[nums[i]] = i;
vector<vector<int>> result;
int endI = nums.size() - 2;
int endJ = nums.size() - 1;
for (int i = 0; i < endI; i++) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
int numI = nums[i];
for (int j = i + 1; j < endJ; j++) {
if (j > 0 && nums[j] == nums[j - 1])
continue;
int numJ = nums[j];
int numK = -(numI + numJ);
if (numPos[numK] > j)
result.emplace_back(vector<int>({numI, numJ, numK}));
}
}
return result;
}
```