# Help on optimization, always becomes o(n^3)

• ``````typedef unordered_map<int, vector<pair<int,int> > >::iterator It;
typedef vector<pair<int,int> >::iterator SetIt;
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &a, int target) {
int n = a.size();

vector<vector<int> > result;
if (n < 4) return result;
std::sort(a.begin(), a.end());
unordered_map<int, vector<pair<int,int> > > m;
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
if (j == i) continue;
m[a[i]+a[j]].push_back(make_pair(i,j));
}
}

for (int i = 0; i < n; ++i) {
if (i > 0 && a[i] == a[i-1]) continue;
for (int j = i+1; j < n; ++j) {
if (j > i+1 && a[j] == a[j-1]) continue;
int s = a[i]+a[j];
It it = m.find(target-s);
if (it == m.end()) continue;
vector<pair<int,int> > pairs = it->second;
int last_k = -1;
int last_m = -1;
for (SetIt setIt = pairs.begin(); setIt != pairs.end(); ++setIt) {
int k = setIt->first;
if (k <= j) continue;
int m = setIt->second;
// we have made sure that the i and j are not repeated, we have to make sure that k and m
// are not repeated, we observe that
if (last_k != -1 && last_m != -1 && a[last_k] == a[k] && a[last_m]==a[m]) continue;
vector<int> cur_vec = {a[i],a[j],a[k],a[m]};
last_k = k;
last_m = m;
result.push_back(cur_vec);
}
}
}
return result;
}
};``````

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