15. 三数之和

标题

给你一个整数数组 nums ，判断是否存在三元组 [nums, nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums + 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
  
• -10^5 <= nums <= 10^5
  

有两种解法，双指针更优，但是为了练习dfs还是先写了dfs
代码

完整代码

1. #include <stdbool.h>
2. #include <stdio.h>
3. #include <stdlib.h>
5. void dfs(int *arr, int index1, int index2, int index3, int arrsize, int **res, int* returnSize) {
6.     if (index3 >= arrsize) {
7.         return;
8.     } else {
9.         if (arr[index1] + arr[index2] + arr[index3] == 0) {
10.             int saved = 0;
11.             for (int i = 0; i < (*returnSize); i++) {
12.                 if (res[i][0] == arr[index1] &&
13.                     res[i][1] == arr[index2] &&
14.                     res[i][2] == arr[index3]) {
15.                     saved = 1;
16.                     break;
17.                 }
18.             }
19.             if (saved == 0) {
20.                 res[(*returnSize)] = (int*)calloc(3, sizeof(int));
21.                 res[(*returnSize)][0] = arr[index1];
22.                 res[(*returnSize)][1] = arr[index2];
23.                 res[(*returnSize)][2] = arr[index3];
24.                 (*returnSize)++;
25.             }
26.         }
27.         dfs(arr, index1, index2, index3 + 1, arrsize, res, returnSize);
28.     }
29.     return;
30. }
32. int cmp(const void *a, const void *b) {
33.     return (*(int*)a) - (*(int*)b);
34. }
36. int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
37.     *returnSize = 0;
38.     qsort(nums, numsSize, sizeof(int), cmp); // 排序数组
39.    
40.     int** res = (int**)calloc(10000, sizeof(int*));
41.     for (int i = 0; i < numsSize - 2; i++) {
42.         for (int j = i + 1; j < numsSize - 1; j++) {
43.             dfs(nums, i, j, j + 1, numsSize, res, returnSize);
44.         }
45.     }
46.    
47.     *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
48.     for (int i = 0; i < (*returnSize); i++) {
49.         (*returnColumnSizes)[i] = 3;
50.     }
51.    
52.     return res;
53. }

复制代码

思路分析

本算法利用深度优先搜刮（DFS）来查找所有满足 nums + nums[j] + nums[k] == 0 的三元组。起首对数组举行排序，然后通过两层循环遍历数组中的每个元素组合，递归检查是否有符合条件的三元组。
拆解分析

• 排序数组：起首对输入数组举行排序，便于后续查找。
  
• 初始化结果存储结构：初始化结果存储结构 res 和 returnSize。
  
• 两层循环遍历数组：通过两层循环遍历数组中的每个元素组合。
  
• 递归查找三元组：在每个组合中，递归检查是否有满足条件的三元组。
  
• 去重：在生存三元组之前，检查是否已经存在，避免重复。
  
• 返回结果：将结果存储在 res 中，并返回结果及其大小。
  

复杂度分析

• 时间复杂度：O(n^3)，其中 n 是数组的长度。必要遍历所有的三元组组合。
  
• 空间复杂度：O(n)，用于存储结果的动态数组和递归调用栈。
  

一题多解

双指针法

双指针法思路分析

• 排序数组：起首对输入数组举行排序。
  
• 遍历数组：遍历数组中的每个元素，固定一个元素 nums。
  
• 双指针查找：在剩余部分用双指针查找两个元素，使得三个元素的和为零。
  
• 去重处置处罚：在移动指针时，跳过重复元素，避免结果中出现重复三元组。
  

双指针法复杂度分析

• 时间复杂度：O(n^2)，排序必要 O(n log n)，遍历和双指针查找必要 O(n^2)。
  
• 空间复杂度：O(1)，除了存储结果的空间外，不必要额外的空间。
  

双指针法代码

1. #include <stdbool.h>
2. #include <stdio.h>
3. #include <stdlib.h>
5. int cmp(const void *a, const void *b) {
6.     return (*(int*)a) - (*(int*)b);
7. }
9. int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
10.     *returnSize = 0;
11.     qsort(nums, numsSize, sizeof(int), cmp); // 排序数组
13.     int** res = (int**)malloc(numsSize * numsSize * sizeof(int*));
14.     for (int i = 0; i < numsSize; i++) {
15.         if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
16.         int left = i + 1;
17.         int right = numsSize - 1;
18.         while (left < right) {
19.             int sum = nums[i] + nums[left] + nums[right];
20.             if (sum == 0) {
21.                 res[*returnSize] = (int*)malloc(3 * sizeof(int));
22.                 res[*returnSize][0] = nums[i];
23.                 res[*returnSize][1] = nums[left];
24.                 res[*returnSize][2] = nums[right];
25.                 (*returnSize)++;
26.                 while (left < right && nums[left] == nums[left + 1]) left++; // 去重
27.                 while (left < right && nums[right] == nums[right - 1]) right--; // 去重
28.                 left++;
29.                 right--;
30.             } else if (sum < 0) {
31.                 left++;
32.             } else {
33.                 right--;
34.             }
35.         }
36.     }
38.     *returnColumnSizes = (int*)malloc(*returnSize * sizeof(int));
39.     for (int i = 0; i < *returnSize; i++) {
40.         (*returnColumnSizes)[i] = 3;
41.     }
43.     return res;
44. }

复制代码

结果

DFS结果

dfs会超时，因为是O(n^3)

双指针结果

正常通过

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。