# C++ implementation with carefully pruning accelerates a lot ! from 100ms to 16ms !

• First thanks to the post from @cx1992

I will just say that with out the 2 using of the

``````  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;
``````

The runing time without these two lines cost 100ms.

But with these lines, cost 16ms !

Here is the final implementation

``````class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
int n=nums.size();
if(n<4)  return result;
sort(nums.begin(), nums.end());
for(int i=0; i<n-3; i++){
if(i>0 && nums[i]==nums[i-1])  continue;
/** cut edge to accelerate the speed **/
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;
/** cut edge to accelerate the speed **/
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;
/** jia bi process **/
int start=j+1, end=n-1;
while(start < end){
int sum=nums[start]+nums[end]+nums[i]+nums[j];
if(sum<target)  start++;
else if(sum>target)  end--;
else{
result.push_back(vector<int>{nums[i], nums[j], nums[start], nums[end]});
start++; end--;
while(nums[start-1]==nums[start] && start<end)  start++;
while(nums[end+1]==nums[end] && start<end)  end--;
}
}
}
}
return result;
}
};``````

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