# 28ms with binary search

• Time complexity O(N^3log(N)) for the fourSum, and O(N^2log(N)) for the threeSum with the same strategy.
Is anyone can obtain the time ~ O(N)-like with the cost of increasing space complexity?

vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n=nums.size(); vector<vector<int> > ans;
if(n<4) return ans;
sort(nums.begin(), nums.end());

int w, x, y, z, ly, ry, a, b, c, d, dc;
for(w=0; w<n-3; w++){
a=nums[w];
if(a+nums[w+1]+nums[w+2]+nums[w+3]>target) return ans;
for(x=w+1; x<n-2; x++){
b=nums[x];
if(a+b+nums[x+1]+nums[x+2]>target) break;
for(z=n-1; z>x+1; z--){
d=nums[z]; ly=x; ry=z; dc=target-a-b-d; y=(ly+ry)/2;c=nums[y];
if(a+b+nums[z-1]+nums[z]<target) break;
while(ly!=y && ry!=y){
if(c<dc) ly=y;
else if(c>dc) ry=y;
else if(c==dc){ ans.push_back(vector<int> {a, b, c, d}); break;}
y=(ly+ry)/2;c=nums[y];
}
while(nums[z]==nums[z-1]) {z--; if(z<3) break;}
}
while(nums[x]==nums[x+1]){x++; if(x>n-3) break;}
}
while(nums[w]==nums[w+1]){w++; if(w>n-4) break;}
}
return ans;
}

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