Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
- The solution set must not contain duplicate quadruplets.
Example:
- Given array S = [1, 0, -1, 0, -2, 2], and target = 0.
- A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
C Solution:
void quick_sort(int *nums, int numsSize) {
if (numsSize < 2) return;
int key = nums[numsSize - 1], i;
for (i = 0; i < numsSize - 1 && nums[i] < key; i++);
if (i == numsSize - 1) {
quick_sort(nums, numsSize - 1);
return;
}
int j;
for (j = i + 1; j < numsSize - 1; j++) {
if (nums[j] < key) {
int tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
i++;
}
}
nums[numsSize - 1] = nums[i];
nums[i] = key;
quick_sort(nums, i);
quick_sort(nums + i + 1, numsSize - i - 1);
}
void twoSum(int *nums, int numsSize, int target, int ***res, int *size, int *returnSize) {
if (2 * nums[0] > target || 2 * nums[numsSize - 1] < target) return;
int l, r;
for (l = 0, r = numsSize - 1; l < r; ) {
if (nums[l] + nums[r] == target) {
if (*size == *returnSize) {
*size += 1000;
*res = realloc(*res, *size * sizeof(int *));
}
(*res)[*returnSize] = malloc(4 * sizeof(int));
(*res)[*returnSize][2] = nums[l];
(*res)[*returnSize][3] = nums[r];
++*returnSize;
for (l++; l < r && nums[l - 1] == nums[l]; l++);
for (r--; l < r && nums[r] == nums[r + 1]; r--);
}
else if (nums[l] + nums[r] > target) r--;
else l++;
}
}
void threeSum(int *nums, int numsSize, int target, int ***res, int *size, int *returnSize) {
if (3 * nums[0] > target || 3 * nums[numsSize - 1] < target) return;
int i, j = *returnSize;
for (i = 0; i < numsSize - 2; ) {
twoSum(nums + i + 1, numsSize - i - 1, target - nums[i], res, size, returnSize);
for (; j < *returnSize; j++) (*res)[j][1] = nums[i];
for (i++; i < numsSize - 2 && nums[i - 1] == nums[i]; i++);
}
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
quick_sort(nums, numsSize);
int size = 1000, **res = malloc(size * sizeof(int *));
*returnSize = 0;
int i, j = *returnSize;
for (i = 0; i < numsSize - 3;) {
threeSum(nums + i + 1, numsSize - i - 1, target - nums[i], &res, &size, returnSize);
for (; j < *returnSize; j++) res[j][0] = nums[i];
for (i++; i < numsSize - 3 && nums[i - 1] == nums[i]; i++);
}
return res;
}
Summary:
- Quite similar to threeSum, even there is a 5Sum, code will not change a lot.
- half 6ms(83.72%), half 9ms(76.74%)
LeetCode: 18. 4Sum
近期评论