# A c++ O(n^2logn) solution

• class Solution {
public:
struct position
{
int sum,l,r;
position(){}
position(int _sum,int _l,int _r): sum(_sum),l(_l),r(_r) {}
bool operator <(const position &a) const
{
return (sum<a.sum)||(sum==a.sum&&l<a.l);
}
};
vector<position> pos;
map<string,int> mp;

``````string tostring(int num)
{
string s="";
while(num)
{
char c=num%10+'0';
s=s+c;
num/=10;
}
return s;
}

int can(int i,int j,int l,int r)
{
return (i!=l)&&(i!=r)&&(j!=l)&&(j!=r);
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<int> twosum;
twosum.clear();
pos.clear();
mp.clear();
vector<vector<int> > ret;
ret.clear();
int sz=nums.size();
for(int i=0;i<sz;i++)
{
for(int j=i+1;j<sz;j++)
{
pos.push_back(position(nums[i]+nums[j],i,j));
twosum.push_back(nums[i]+nums[j]);
}
}
sort(pos.begin(),pos.end());
sort(twosum.begin(),twosum.end());
int i=0,j=i+1;
for(i=0;i<sz;i++)
{
for(j=i+1;j<sz;j++)
{
int curtwo=nums[i]+nums[j];
int curtwopos=(2*sz-j-2)*(j+1)/2;
int findpos=lower_bound(twosum.begin(),twosum.end(),target-curtwo)-twosum.begin();
while(findpos<twosum.size()&&twosum[findpos]==target-curtwo)
{
vector<int> newans;
newans.clear();
int l=pos[findpos].l,r=pos[findpos].r;
int n1,n2,n3,n4;
n1=nums[i],n2=nums[j],n3=nums[l],n4=nums[r];
newans.push_back(n1),newans.push_back(n2),newans.push_back(n3),newans.push_back(n4);
sort(newans.begin(),newans.end());
string s="";
s=tostring(newans[0])+","+tostring(newans[1])+","+tostring(newans[2])+","+tostring(newans[3]);
if(can(i,j,l,r)&&mp[s]==0)
{
mp[s]=1;
ret.push_back(newans);
}
findpos++;
}
}
while(i+1<sz&&nums[i+1]==nums[i]) i++;
}
return ret;
}
``````

};

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