当前位置：首页 > news >正文

15. 三数之和

news 来源：原创 2025/7/17 17:52:37

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000

解题思路：

1.排序数组：首先对数组进行排序，这样可以方便地使用双指针技术来寻找三元组，并且有助于跳过重复的元素。
2. 固定一个元素，使用双指针寻找其他两个元素：遍历数组，对于每个元素nums[i]，使用双指针left和right分别指向i+1和数组末尾，寻找满足nums[i] + nums[left] + nums[right] == 0的三元组。
3. 跳过重复元素：在遍历过程中，如果遇到重复的元素，跳过它们以避免重复的三元组。
4. 存储结果：每当找到满足条件的三元组时，将其存储到结果列表中。

// 比较函数，用于qsort排序
int compare(const void *a, const void *b) {return (*(int*)a - *(int*)b); // 升序排序
}// 三数之和函数
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {// 首先对数组进行排序（升序）qsort(nums, numsSize, sizeof(int), compare);// 分配足够大的空间来存储结果（最坏情况下可能有n^2个三元组）int maxTriplets = numsSize * numsSize;int** result = (int**)malloc(maxTriplets * sizeof(int*)); // 存储结果数组*returnColumnSizes = (int*)malloc(maxTriplets * sizeof(int)); // 存储每个结果的大小*returnSize = 0; // 初始化返回结果的数量为0// 遍历数组，i作为第一个数的索引for (int i = 0; i < numsSize - 2; i++) {// 跳过重复的nums[i]（避免重复三元组）if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 设置双指针：left从i+1开始，right从末尾开始int left = i + 1;int right = numsSize - 1;// 双指针遍历while (left < right) {// 计算当前三个数的和int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {// 找到满足条件的三元组result[*returnSize] = (int*)malloc(3 * sizeof(int)); // 分配内存存储三元组result[*returnSize][0] = nums[i]; // 第一个数result[*returnSize][1] = nums[left]; // 第二个数result[*returnSize][2] = nums[right]; // 第三个数(*returnColumnSizes)[*returnSize] = 3; // 设置该结果的大小为3(*returnSize)++; // 增加结果计数// 跳过重复的nums[left]和nums[right]（避免重复三元组）while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}// 移动指针继续寻找left++;right--;} else if (sum < 0) {// 和太小，左指针右移（因为数组已排序）left++;} else {// 和太大，右指针左移right--;}}}return result; // 返回结果数组
}

本次实验实现了寻找数组中所有和为0且不重复的三元组的算法。通过排序数组和使用双指针技术，我们有效地减少了时间复杂度，确保算法在O(n²)时间内完成。关键步骤包括：
1. 数组排序：首先对输入数组进行升序排序，为双指针法创造条件。
2. 双指针遍历：固定一个元素后，使用双指针在剩余数组中寻找满足条件的另外两个元素。
3. 去重处理：在遍历过程中跳过重复元素，避免生成重复的三元组。
4. 动态内存管理：合理分配和释放内存，确保程序运行效率。

相关文章：