# After pruning in 3-Sum section decrease the time cost from 28ms to 8ms as best submission in C, well-commented

• ``````void sort(int* nums, int begin, int end)
{
int l = begin;
int r = end;
int v = nums[l+(r-l)/2];
while(l <= r)
{
while(nums[l] < v) l++;
while(nums[r] > v) r--;
if(l <= r)
{
int t = nums[l];
nums[l] = nums[r];
nums[r] = t;
l++; r--;
}
}
if(begin < r)
sort(nums, begin, r);
if(l < end)
sort(nums, l, end);
}

//AC - 8ms;
int** fourSum(int* nums, int size, int target, int* returnSize)
{
sort(nums, 0, size-1);
int** arr = (int**)malloc(sizeof(int*));
*returnSize = 0;
for(int i = 0; i < size-3; i++)
{
if(i && nums[i]==nums[i-1]) continue;
int t0 = target-nums[i]; //target for 3Sum;
for(int j = i+1; j < size-2; j++)
{
if(j!=i+1 && nums[j]==nums[j-1]) continue; //the start position should be handled carefully, it's i+1 while removing redundancy;
int t1 = t0-nums[j]; //target for 2Sum;
if(nums[j+1]+nums[j+2] > t1) break; //the possible least sum is even bigger than the target - just try the next first candidate - i+1;
if(nums[size-1]+nums[size-2] < t1) continue; //the possible maximal sum is smaller than the target - just try the next second candidate to make it bigger - j+1;
int l = j+1;
int r = size-1;
while(l < r) //2Sum problem;
{
int t2 = nums[l]+nums[r];
if(t1 > t2) l++;
else if(t1 < t2) r--;
else
{
if(!*returnSize || (*returnSize && (nums[i]!=arr[*returnSize-1][0]
|| nums[j]!=arr[*returnSize-1][1]
|| nums[l]!=arr[*returnSize-1][2])))
{
*returnSize += 1;
arr = (int**)realloc(arr, sizeof(int*)*(*returnSize));
arr[*returnSize-1] = (int*)malloc(sizeof(int)*4);
arr[*returnSize-1][0] = nums[i];
arr[*returnSize-1][1] = nums[j];
arr[*returnSize-1][2] = nums[l];
arr[*returnSize-1][3] = nums[r];
}
l++;
}
}
}
}
return arr;
}``````

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