15. 三数之和
标题给你一个整数数组 nums ，判断是否存在三元组 , nums, nums] 满足 i != j、i != k 且 j != k ，同时还满足 nums + nums + nums == 0。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
[*]nums + nums + nums = (-1) + 0 + 1 = 0
[*]nums + nums + nums = 0 + 1 + (-1) = 0
[*]nums + nums + nums = (-1) + 2 + (-1) = 0
不同的三元组是 [-1,0,1] 和 [-1,-1,2]。注意，输出的顺序和三元组的顺序并不紧张。
示例 2：
输入：nums =
输出：[]
解释：唯一可能的三元组和不为 0。
示例 3：
输入：nums =
输出：[]
解释：唯一可能的三元组和为 0。
提示
[*]3 <= nums.length <= 3000
[*]-10^5 <= nums <= 10^5
有两种解法，双指针更优，但是为了练习dfs还是先写了dfs
代码
完整代码
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
void dfs(int *arr, int index1, int index2, int index3, int arrsize, int **res, int* returnSize) {
if (index3 >= arrsize) {
return;
} else {
if (arr + arr + arr == 0) {
int saved = 0;
for (int i = 0; i < (*returnSize); i++) {
if (res == arr &&
res == arr &&
res == arr) {
saved = 1;
break;
}
}
if (saved == 0) {
res[(*returnSize)] = (int*)calloc(3, sizeof(int));
res[(*returnSize)] = arr;
res[(*returnSize)] = arr;
res[(*returnSize)] = arr;
(*returnSize)++;
}
}
dfs(arr, index1, index2, index3 + 1, arrsize, res, returnSize);
}
return;
}
int cmp(const void *a, const void *b) {
return (*(int*)a) - (*(int*)b);
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
qsort(nums, numsSize, sizeof(int), cmp); // 排序数组
int** res = (int**)calloc(10000, sizeof(int*));
for (int i = 0; i < numsSize - 2; i++) {
for (int j = i + 1; j < numsSize - 1; j++) {
dfs(nums, i, j, j + 1, numsSize, res, returnSize);
}
}
*returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
for (int i = 0; i < (*returnSize); i++) {
(*returnColumnSizes) = 3;
}
return res;
}
思路分析
本算法利用深度优先搜刮（DFS）来查找所有满足 nums + nums + nums == 0 的三元组。起首对数组举行排序，然后通过两层循环遍历数组中的每个元素组合，递归检查是否有符合条件的三元组。
拆解分析
[*]排序数组：起首对输入数组举行排序，便于后续查找。
[*]初始化结果存储结构：初始化结果存储结构 res 和 returnSize。
[*]两层循环遍历数组：通过两层循环遍历数组中的每个元素组合。
[*]递归查找三元组：在每个组合中，递归检查是否有满足条件的三元组。
[*]去重：在生存三元组之前，检查是否已经存在，避免重复。
[*]返回结果：将结果存储在 res 中，并返回结果及其大小。
复杂度分析
[*]时间复杂度：O(n^3)，其中 n 是数组的长度。必要遍历所有的三元组组合。
[*]空间复杂度：O(n)，用于存储结果的动态数组和递归调用栈。
一题多解
双指针法
双指针法思路分析
[*]排序数组：起首对输入数组举行排序。
[*]遍历数组：遍历数组中的每个元素，固定一个元素 nums。
[*]双指针查找：在剩余部分用双指针查找两个元素，使得三个元素的和为零。
[*]去重处置处罚：在移动指针时，跳过重复元素，避免结果中出现重复三元组。
双指针法复杂度分析
[*]时间复杂度：O(n^2)，排序必要 O(n log n)，遍历和双指针查找必要 O(n^2)。
[*]空间复杂度：O(1)，除了存储结果的空间外，不必要额外的空间。
双指针法代码
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int*)a) - (*(int*)b);
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
qsort(nums, numsSize, sizeof(int), cmp); // 排序数组
int** res = (int**)malloc(numsSize * numsSize * sizeof(int*));
for (int i = 0; i < numsSize; i++) {
if (i > 0 && nums == nums) continue; // 去重
int left = i + 1;
int right = numsSize - 1;
while (left < right) {
int sum = nums + nums + nums;
if (sum == 0) {
res[*returnSize] = (int*)malloc(3 * sizeof(int));
res[*returnSize] = nums;
res[*returnSize] = nums;
res[*returnSize] = nums;
(*returnSize)++;
while (left < right && nums == nums) left++; // 去重
while (left < right && nums == nums) right--; // 去重
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
*returnColumnSizes = (int*)malloc(*returnSize * sizeof(int));
for (int i = 0; i < *returnSize; i++) {
(*returnColumnSizes) = 3;
}
return res;
}
结果
DFS结果
dfs会超时，因为是O(n^3)
https://img-blog.csdnimg.cn/direct/7fd929bf3d9d44e9a72cd970618cc41a.png
双指针结果
正常通过
https://img-blog.csdnimg.cn/direct/1232aabd982345a283072376a472f2b8.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]