# Proved to be a best O(n^2), worst O(n^3) solution

• with a map to record pairs of indexes with same sum.
iterator the first 2 number i, j, and find remain in the map, if the first index of the pair if bigger than j, than we found a result.

when for each 2sum there is only one pair of indexes, the time complexity is O(n^2)

for a corner case: 1,1,1,1,1,1,1,1
the map is:

key vector length

2 n*(n-1)/2

how ever there is only one valid i=1,j=1, time complexity is O(n^2)

for the worst case: 1,2,3,4,5,6,7,8,9
the map is:

key vector length

3 1

4 1

5 2

6 2

7 3

8 3

9 4

10 4

11 4

12 3

13 3

14 2

15 2

16 1

17 1

the average vector length is n/4. therefore time complexity is O(n^3)

``````vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int> > res;
int n=num.size();
if(n==0)return res;
sort(num.begin(),num.end());
unordered_map<int, vector<pair<int,int>> > mp;
unordered_map<int,vector<pair<int,int>> >::iterator it;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
mp[num[i]+num[j]].push_back(pair<int,int>(i,j));
}
}

vector<int> tmp;
int sum=0;
for(int i=0;i<n;i++)
{
if(i>0&&num[i]==num[i-1])continue;
sum+=num[i];
tmp.push_back(num[i]);
for(int j=i+1;j<n;j++)
{
if(j>i+1&&num[j]==num[j-1])continue;
sum+=num[j];
it=mp.find(target-sum);
if(it!=mp.end())
{
tmp.push_back(num[j]);
int vsize=it->second.size();
for(int k=vsize-1;k>=0;k--)
{
if(it->second[k].first<=j)break;
if(k+1<vsize&&num[it->second[k].first]==num[it->second[k+1].first])continue;
tmp.push_back(num[it->second[k].first]);
tmp.push_back(num[it->second[k].second]);
res.push_back(tmp);
tmp.pop_back();
tmp.pop_back();
}
tmp.pop_back();
}
sum-=num[j];
}
tmp.pop_back();
sum-=num[i];
}
return res;
}
``````

another solution is obviously O(n^3), actually it's faster than the above one(372ms):

`````` vector<vector<int> > fourSum(vector<int> &num, int target) {
vector<vector<int> > res;
int n=num.size();
if(n==0)return res;
sort(num.begin(),num.end());
unordered_map<int,int> mp;
unordered_map<int,int> mp2;
unordered_map<int,int>::iterator it;
for(int i=0;i<n;i++)
{
mp[num[i]]=i;
for(int j=i+1;j<n;j++)
{
mp2[num[i]+num[j]]=i;
}
}

vector<int> tmp;
int sum=0;
for(int i=0;i<n;i++)
{
if(i>0&&num[i]==num[i-1])continue;
sum+=num[i];
tmp.push_back(num[i]);
for(int j=i+1;j<n;j++)
{
if(j>i+1&&num[j]==num[j-1])continue;
sum+=num[j];
it=mp2.find(target-sum);
if(it!=mp2.end()&&it->second>j)
{
tmp.push_back(num[j]);
for(int k=j+1;k<n;k++)
{
if(k>j+1&&num[k]==num[k-1])continue;
sum+=num[k];
it=mp.find(target-sum);
if(it!=mp.end()&&it->second>k)
{
tmp.push_back(num[k]);
tmp.push_back(it->first);
res.push_back(tmp);
tmp.pop_back();
tmp.pop_back();
}
sum-=num[k];
}
tmp.pop_back();
}
sum-=num[j];
}
tmp.pop_back();
sum-=num[i];
}
return res;
}``````

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