ToB企服应用市场:ToB评测及商务社交产业平台

标题: 15. 三数之和 [打印本页]
作者: 万万哇    时间: 2024-6-27 06:47
标题: 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]]
解释：

不同的三元组是 [-1,0,1] 和 [-1,-1,2]。注意，输出的顺序和三元组的顺序并不紧张。
示例 2：

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

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


有两种解法，双指针更优，但是为了练习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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4