# Why this hashing solution keeps TLE?

• ``````#include <utility>
#include <unordered_map>
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int> > result;
// if the num's size is less than 4, clearly we should return
if (num.size() < 4)
return result;
// mip stores values pairs
unordered_map<int, vector<pair<int, int> > > mip;
// isSearched stores whether a given value has been searched or not
unordered_map<int, bool> isSearched;

// for any num[i], num[j], hash it into mip
// key: num[i]+num[j]
// value: a vector storing pair(i, j)
for (int i{0}; i < num.size(); ++i) {
for (int j{i+1}; j < num.size(); ++j) {
mip[num[i]+num[j]].push_back(make_pair(i, j));
}
}

// loop against mip
for (auto &kv: mip) {
// fst_half: the sum of two numbers
int fst_half{kv.first};
// snd_half: the sum of another two numbers
// fst_half + snd_half == target
int snd_half{target-kv.first};
// if already searched, we continue
if (isSearched[fst_half] || isSearched[snd_half])
continue;
isSearched[fst_half] = isSearched[snd_half] = true;
if (mip[snd_half].size() != 0) {
// we take one pair from mip[fst_half].second and one pair from mip[snd_half].second
// and combine them together
for (size_t i{0}, j{0}; i < kv.second.size(); ++i) {
// if fst_half == snd_half, we set j = i+1 to eliminate seemingly duplication
if (fst_half == snd_half)
j = i+1;
else
j = 0;
for ( ; j < mip[snd_half].size(); ++j) {
int posa{kv.second[i].first}, posb{kv.second[i].second}, \
posc{mip[snd_half][j].first}, posd{mip[snd_half][j].second};
if (posa != posc && posa != posd && posb != posd && posb != posc) {
result.push_back(vector<int>());
result.back().push_back(num[posa]);
result.back().push_back(num[posb]);
result.back().push_back(num[posc]);
result.back().push_back(num[posd]);
sort(result.back().begin(), result.back().end());
}
}
}
}

}
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
};``````

• sort(result.back().begin(), result.back().end());

This is unnecessarily costly.

It is easier and more efficient if you sort the num earlier in the beginning.

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