A typical best-solution accepted as 8ms in C, well-commented


  • 5
    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;
    }

  • 1
    Y
     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.


  • 1

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


  • 0
    F
     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;
    }
    

Log in to reply
 

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