# A typical best-solution accepted as 8ms 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]))) //avoid duplicates;
{
*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;
}``````

• `````` if(nums[j+1]+nums[j+2] > t1) break;
if(nums[size-1]+nums[size-2] < t1) continue;
``````

these two lines hava a efficient influence on the speed.It makes my 62ms java code to 10ms.

• Yeah! Pruning lots of redundant checking. B.T.W. you should not comment in answer section. Not cool, man.

• `````` if(nums[j+1]+nums[j+2] > t1) break;
if(nums[size-1]+nums[size-2] < t1) continue;
``````

It really happened; with these two statements, the run-time of my C solution changed from 16ms to 8ms.

``````/**
* Return an array of arrays of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
void quicksort(int *nums, int numsSize) {
if (numsSize < 2) return;
int *m, *p, *e = nums + numsSize - 1;
for (m = nums; m < e && *m < *e; m++);
if (m == e) quicksort(nums, numsSize - 1);
else {
for (p = m + 1; p < e; p++) {
if (*p < *e) {
int tmp = *m;
*m++ = *p;
*p = tmp;
}
}
int tmp = *e;
*e = *m;
*m = tmp;
quicksort(nums, m - nums);
quicksort(m + 1, e - m);
}
}
void save(int fisrt, int second, int left, int right, int ***ret, int *pos, int *size) {
if (*pos >= *size) {
*size += 1024;
*ret = realloc(*ret, (*size * sizeof(int *)));
}
(*ret)[*pos] = malloc(4 * sizeof(int));
(*ret)[*pos][0] = fisrt;
(*ret)[*pos][1] = second;
(*ret)[*pos][2] = left;
(*ret)[*pos][3] = right;
(*pos)++;
}
void twoSum(int *nums, int numsSize, int first, int second, int target, int ***ret, int *pos, int *size) {
int *l = nums, *r = nums + numsSize - 1;
while(l < r) {
if (*l + *r < target) {
l++;
continue;
}
if (*l + *r > target) {
r--;
continue;
}
save(first, second, *l, *r, ret, pos, size);
int *p, *q;
for (p = l; p < r && *p == *l; p++) for (q = r; p < q && *q == *r; q--);
l = p;
r = q;
}
}
int** threeSum(int* nums, int numsSize, int first, int target, int ***ret, int *pos, int *retSize) {
int pre_tgt = target - nums[0];
twoSum(nums + 1, numsSize - 1, first, nums[0], pre_tgt, ret, pos, retSize);
int i;
for (i = 1; i < numsSize - 2; i++) {
int tgt = target - nums[i];
if (tgt == pre_tgt) continue;
else pre_tgt = tgt;
if (nums[i + 1] + nums[i + 2] > tgt) break;
if (nums[numsSize - 1]+nums[numsSize - 2] < tgt) continue;
twoSum(nums + i + 1, numsSize - i - 1, first, nums[i], tgt, ret, pos, retSize);
}
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
if (numsSize < 4) {
*returnSize = 0;
return 0;
}
int retSize = 1024, pos = 0;
int **ret = malloc(retSize * sizeof(int *));
quicksort(nums, numsSize);
int pre_tgt = target - nums[0];
threeSum(nums + 1, numsSize - 1, nums[0], pre_tgt, &ret, &pos, &retSize);
int i;
for (i = 1; i < numsSize - 3; i++) {
int tgt = target - nums[i];
if (tgt == pre_tgt) continue;
else pre_tgt = tgt;
threeSum(nums + i + 1, numsSize - i - 1, nums[i], tgt, &ret, &pos, &retSize);
}
*returnSize = pos;
return ret;
}
``````

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