18. 4Sum
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
- 0 <= a, b, c, d < n
- a, b, c, and d are distinct.
- nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Example 2:
Constraints:
- 1 <= nums.length <= 200
- − 1 0 9 < = n u m s [ i ] < = 1 0 9 -10^9 <= nums[i] <= 10^9 −109<=nums[i]<=109
- − 1 0 9 < = t a r g e t < = 1 0 9 -10^9 <= target <= 10^9 −109<=target<=109
From: LeetCode
Link: 18. 4Sum
Solution:
Ideas:
- Sorting: The array is sorted to allow efficient searching and to easily skip duplicates.
- Nested Loops with Two-pointer Technique: The function uses a nested loop for the first two elements of the quadruplet and then applies the two-pointer approach for the remaining two elements.
- Avoiding Duplicates: To ensure all quadruplets are unique, the function skips over duplicate elements, similar to the approach used in 3Sum.
- Memory Management: The function initializes with a set capacity for result storage, reallocating as necessary. This needs careful handling to avoid memory leaks. Users of this function must free the memory allocated for each quadruplet as well as the result array and column sizes array.
Code:
// Comparator function for qsort
int compare(const void *a, const void *b) {
int int_a = *((int*)a);
int int_b = *((int*)b);
return int_a > int_b ? 1 : int_a < int_b ? -1 : 0;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
qsort(nums, numsSize, sizeof(int), compare);
*returnSize = 0;
int capacity = 500; // Adjust this capacity according to the expected number of results
int** result = (int**)malloc(capacity * sizeof(int*));
*returnColumnSizes = (int*)malloc(capacity * sizeof(int));
for (int i = 0; i < numsSize - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates
for (int j = i + 1; j < numsSize - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates
int left = j + 1;
int right = numsSize - 1;
while (left < right) {
long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; // use long long to prevent overflow
if (sum == target) {
// Save the quadruplet
if (*returnSize == capacity) {
// Increase capacity if needed
capacity *= 2;
result = (int**)realloc(result, capacity * sizeof(int*));
*returnColumnSizes = (int*)realloc(*returnColumnSizes, capacity * sizeof(int));
}
result[*returnSize] = (int*)malloc(4 * sizeof(int));
result[*returnSize][0] = nums[i];
result[*returnSize][1] = nums[j];
result[*returnSize][2] = nums[left];
result[*returnSize][3] = nums[right];
(*returnColumnSizes)[*returnSize] = 4;
(*returnSize)++;
// Skip duplicates
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}