C语言编程--15.四数之和

题目：

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

1. 0 <= a, b, c, d < n
2. a、b、c 和 d 互不相同
3. 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

代码：

#include <stdlib.h>// 比较函数，用于 qsort 对数组进行排序
// pa 和 pb 是指向要比较元素的指针
// 返回值为 1 表示 a > b，返回 -1 表示 a < b
int cmp(const void* pa, const void* pb)
{int a = *(int*)pa;  // 将 pa 指针指向的元素转换为 int 类型并赋值给 aint b = *(int*)pb;  // 将 pb 指针指向的元素转换为 int 类型并赋值给 breturn a > b ? 1 : -1;  // 如果 a 大于 b 返回 1，否则返回 -1
}// 四数之和函数，用于找出数组中所有不重复的四元组，使得它们的和等于目标值
// nums 是输入的整数数组
// numsSize 是数组的长度
// target 是目标和
// returnSize 是返回的四元组的数量
// returnColumnSizes 是每个四元组的长度（固定为 4）
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {qsort(nums, numsSize, sizeof(int), cmp);  // 对数组进行排序，方便后续去重和双指针操作int base = 100;  // 初始分配的结果数组的容量int **result = (int**)malloc(sizeof(int*) * base);  // 动态分配存储四元组的二维数组*returnColumnSizes = (int*)malloc(sizeof(int) * base);  // 动态分配存储每个四元组长度的数组*returnSize = 0;  // 初始化返回的四元组数量为 0// 如果数组长度小于 4，直接返回空结果if (numsSize < 4) {return result;}// 外层循环，固定第一个数for(int i = 0; i < numsSize - 3; i++) {// 跳过重复的第一个数，避免结果中出现重复的四元组if (i > 0 && nums[i] == nums[i - 1])continue;// 第二层循环，固定第二个数for(int j = i + 1; j < numsSize - 2; j++) {// 跳过重复的第二个数，避免结果中出现重复的四元组if (j > i + 1 && nums[j] == nums[j - 1])continue;int l = j + 1;  // 左指针，指向第二个数的下一个位置int r = numsSize - 1;  // 右指针，指向数组的最后一个位置// 双指针法，在剩余的元素中寻找满足条件的第三个数和第四个数while (l < r) {// 计算四个数的和，使用 long long 类型避免整数溢出long long sum = (long long)nums[i] + (long long)nums[j] + (long long)nums[l] + (long long)nums[r];long long temp = sum - target;  // 计算当前和与目标值的差值// 如果差值为 0，说明找到了一个满足条件的四元组if (temp == 0) {result[*returnSize] = (int*)malloc(sizeof(int) * 4);  // 为新的四元组分配内存(*returnColumnSizes)[*returnSize] = 4;  // 设置该四元组的长度为 4result[*returnSize][0] = nums[i];  // 存储第一个数result[*returnSize][1] = nums[j];  // 存储第二个数result[*returnSize][2] = nums[l];  // 存储第三个数result[*returnSize][3] = nums[r];  // 存储第四个数(*returnSize)++;  // 四元组数量加 1// 如果结果数组的容量不够，扩大容量if (*returnSize == base) {base *= 2;  // 容量翻倍result = (int**)realloc(result, sizeof(int*) * base);  // 重新分配结果数组的内存*returnColumnSizes = (int*)realloc(*returnColumnSizes, sizeof(int) * base);  // 重新分配每个四元组长度数组的内存}int a = nums[l];  // 记录当前左指针指向的数int b = nums[r];  // 记录当前右指针指向的数// 跳过重复的第三个数while (nums[l] == a && l < r)l++;// 跳过重复的第四个数while (nums[r] == b && l < r)r--;} // 如果当前和大于目标值，右指针左移else if (temp > 0) {r--;} // 如果当前和小于目标值，左指针右移else {l++;}   }}}return result;  // 返回存储所有满足条件四元组的二维数组
}

代码分析：

优点

1. 排序和双指针法：通过对数组进行排序，然后使用双指针法，将原本的暴力枚举 O(n⁴)的时间复杂度降低到了O(n³)，提高了算法的效率。
2. 去重处理：在每一层循环中都进行了去重处理，避免了结果中出现重复的四元组，保证了结果的正确性。
3. 动态内存分配：使用 malloc 和 realloc 动态分配内存，根据实际结果的数量调整内存大小，避免了内存的浪费。
4. 处理整数溢出：在计算四个数的和时，使用 long long 类型，避免了整数溢出的问题，提高了代码的健壮性。

缺点

1. 时间复杂度较高：虽然使用了双指针法将时间复杂度从 O(n⁴)的时间复杂度降低到了O(n³)，但对于大规模数据，仍然可能会超时。
2. 内存管理复杂：使用了动态内存分配，需要手动管理内存，容易出现内存泄漏的问题。在使用完返回的结果数组后，需要调用者手动释放内存。
3. 提前剪枝不足：代码中虽然有一些基本的逻辑，但没有充分利用排序后的数组特性进行更有效的提前剪枝，例如可以在某些情况下提前终止循环，减少不必要的计算。