# My 16ms c++ code

• ``````class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> total;
int n = nums.size();
sort(nums.begin(),nums.end());
for(int i=0;i<n-3;i++)
{
if(i>0&&nums[i]==nums[i-1]) continue;
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
for(int j=i+1;j<n-2;j++)
{
if(j>i+1&&nums[j]==nums[j-1]) continue;
if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
int left=j+1,right=n-1;
while(left<right){
int sum=nums[left]+nums[right]+nums[i]+nums[j];
if(sum<target) left++;
else if(sum>target) right--;
else{
total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
do{left++;}while(nums[left]==nums[left-1]&&left<right);
do{right--;}while(nums[right]==nums[right+1]&&left<right);
}
}
}
}
}
};``````

• cooooooooooooooooooooooooooooool!

• Good Idea. The key point is to add checking at the start of the loop.
At loop 1:

``````if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
``````

At loop 2:

``````if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
``````

Then we skip this loop to avoid a waste of time.

• Key idea is still as others with two pointers. But it uses early pruning as you just pointed out.

• if(i>0&&nums[i]==nums[i-1]) continue;
What it's meaning?
in this case [-1,-1,-1,0,1,2,3] 0 ,your code sames like will skip [-1,-1,0,2] answer after find [
-1,-1,-1,3 ].

• Great idea!!!!!

• This is a very good optimization for general cases, but it doesn't help on worst cases, I think the time complexity of this algorithm is still O(n^3logn) right?

• clean implementation!

• You cutting edge accelerate the speed is really specific......

``````  if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;

if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
``````

Can accelerate the code from 100ms to 16ms !

• You are right it accelerate from 100ms to 16ms ! Pruning is really useful.

• smart break and continue statements!

• your pruning is excellent!!!!!! reduce 108ms to 16ms

• pruning is the king!

• Enclosing my KSum yet still best submission here combining portability and performance perfectly in this case.

``````class Solution {
private:
const int K = 4;
int size;
void search(const vector<int>& nums, int pos, int k, int target, vector<int>& v, vector<vector<int>>& vv)
{
if(k == 2)
{
int l = pos, r = size-1;
while(l < r)
{
int t = nums[l]+nums[r];
if(t > target) r--;
else if(t < target) l++;
else
{
v.push_back(nums[l++]);
v.push_back(nums[r--]);
vv.push_back(v);
v.pop_back(), v.pop_back();
while(l<r && nums[l]==nums[l-1]) l++;
while(l<r && nums[r]==nums[r+1]) r--;
}
}
}
else
{
for(int j = pos; j <= size-k; ++j)
{
int sum = 0;
for(int i = j; i < k+j; ++i) sum += nums[i];
if(sum > target) break;
sum = nums[j];
for(int i = 0; i < k-1; ++i) sum += nums[size-1-i];
if(sum < target) continue;
v.push_back(nums[j]);
search(nums, j+1, k-1, target-nums[j], v, vv);
v.pop_back();
while(j<=size-k && nums[j+1]==nums[j]) j++;
}
}
}
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
sort(nums.begin(), nums.end());
size = nums.size();
vector<int> v;
vector<vector<int>> vv;
search(nums, 0, K, target, v, vv);
return vv;
}
};
``````

• why I use

total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});

Run Code Status diaplayed :Memory Limit Exceeded

• @pointless Show your `code` first.

• @LHearen

``````class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums,int target) {
vector<vector<int>>s;
while(nums.size()<=3)return s;
int n=nums.size();
sort(nums.begin(),nums.end());
//int init=nums[0]+nums[1]+nums[2]+nums[3];
//if(init>target)return s;
//else if(init==target)s.push_back(vector<int>{nums[0],nums[1],nums[2],nums[3]});

for(int i=0;i<n-3;i++){
if(i>0&&nums[i]==nums[i-1]) continue;
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
for(int j=i+1;j<n-2;j++){
if(j>i+1&&nums[j]==nums[j-1]) continue;
if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
int k=j+1;
int l=n-1;
while(k<l){
int sum=nums[i]+nums[k]+nums[l]+nums[j];
if(sum==target){
//vector<int>tmp(4,0);
//tmp[0]=nums[i];
//tmp[1]=nums[j];
//tmp[2]=nums[k];
//tmp[3]=nums[l];
//s.push_back(tmp);
s.push_back(vector<int>{nums[i],nums[j],nums[k],nums[l]});
//while(k<l&&nums[k]==tmp[2])k++;
//while(k<l&&nums[l]==tmp[3])l--;
while(k<l&&nums[k]==nums[k-1])k++;
while(k<l&&nums[l]==nums[l-1])l--;
//continue;
}
else (sum>target)?l--:k++;
}
}

}

//}
return s;
}

};
``````

• @pointless Your code is fixed now, be careful next time. Good luck.

``````if(sum==target)
{
s.push_back(vector<int>{nums[i],nums[j],nums[k++],nums[l--]});
while(k<l&&nums[k]==nums[k-1])k++;
while(k<l&&nums[l]==nums[l+1])l--;
}
``````

• @LHearen oh，I see.
Thanks.

• Awesome!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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