力扣第十八题——四数之和
内容介绍
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]提示：
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
完整代码
int comp(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
int** quadruplets = malloc(sizeof(int*) * 1001);
*returnSize = 0;
*returnColumnSizes = malloc(sizeof(int) * 1001);
if (numsSize < 4) {
return quadruplets;
}
qsort(nums, numsSize, sizeof(int), comp);
int length = numsSize;
for (int i = 0; i < length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
for (int j = i + 1; j < length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
int left = j + 1, right = length - 1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
int* tmp = malloc(sizeof(int) * 4);
tmp[0] = nums[i], tmp[1] = nums[j], tmp[2] = nums[left], tmp[3] = nums[right];
(*returnColumnSizes)[(*returnSize)] = 4;
quadruplets[(*returnSize)++] = tmp;
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
left++;
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return quadruplets;
}
思路详解
整体思路
- 首先对数组进行排序，以便后续可以使用双指针法快速查找。
- 使用四重循环遍历数组，但通过一些剪枝操作减少不必要的遍历。
- 在最内层循环中使用双指针法查找剩余的两个数，以减少时间复杂度。
代码详解
1. 排序
qsort(nums, numsSize, sizeof(int), comp);
使用快速排序对数组进行排序，便于后续查找。
2. 第一层循环
for (int i = 0; i < length - 3; i++) {
遍历数组，固定第一个数。由于需要四个数，所以循环到 length - 3 即可。
3. 去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
如果当前数与前一个数相同，则跳过，以避免重复的四元组。
4. 剪枝
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
如果当前数加上最小的三个数大于目标值，则后面的数都不可能组成四元组，直接退出循环。同理，如果当前数加上最大的三个数小于目标值，则当前数不合适，继续下一轮循环。
5. 第二层循环
for (int j = i + 1; j < length - 2; j++) {
固定第二个数，从 i + 1 开始遍历。
6. 去重与剪枝（同上）
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
7. 双指针法
int left = j + 1, right = length - 1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
// 找到一个四元组，保存结果
} else if (sum < target) {
left++;
} else {
right--;
}
}
使用双指针法在剩余部分查找剩余的两个数。如果四数之和等于目标值，则保存结果并移动指针以去重；如果小于目标值，则左指针右移；如果大于目标值，则右指针左移。
8. 保存结果
int* tmp = malloc(sizeof(int) * 4);
tmp[0] = nums[i], tmp[1] = nums[j], tmp[2] = nums[left], tmp[3] = nums[right];
(*returnColumnSizes)[(*returnSize)] = 4;
quadruplets[(*returnSize)++] = tmp;
当找到四元组时，分配内存保存结果，并更新返回数组的大小和列数。
总结
该代码通过排序、剪枝和双指针法，有效地解决了四数之和问题，时间复杂度从暴力解法的 O(n^4) 降低到 O(n^3)。
知识点精炼
-
问题描述：给定一个整数数组和一个目标值，找出数组中所有不重复的四元组，使得这四个整数的和等于目标值。
-
排序：首先对数组进行排序，这是解决四数之和问题的关键步骤，有助于后续的剪枝和双指针操作。
-
剪枝：在遍历过程中，通过判断当前数与最小/最大三个数的和是否超过目标值，来提前终止循环，减少不必要的计算。
-
去重：在固定前两个数时，如果当前数与前一个数相同，则跳过，以避免产生重复的四元组。
-
双指针法：在固定前两个数后，使用双指针法在剩余部分查找剩余的两个数，降低时间复杂度。
-
时间复杂度：排序的时间复杂度为 O(nlogn)，四重循环的时间复杂度为 O(n^3)，总体时间复杂度为 O(n^3)。
-
空间复杂度：主要为存储结果数组的空间，最坏情况下为 O(n^2)。
-
注意事项：
- 防止整数溢出：在计算四数之和时，使用 long 类型存储中间结果。
- 内存管理：动态分配内存时，记得释放。
原文地址：https://blog.csdn.net/m0_74932528/article/details/140547123
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！