算法笔记-两数之和、三数之和、四数之和（LeetCode)

青旅半醒 2023-02-14 02:29 129阅读 0赞

两数之和

1.两数之和
题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

  1. 给定 nums = [2, 7, 11, 15], target = 9
  3. 因为 nums[0] + nums[1] = 2 + 7 = 9
  4. 所以返回 [0, 1]

代码：

  1. /**
  2.  * Note: The returned array must be malloced, assume caller calls free().
  3.  */
  4. int* twoSum(int* nums, int numsSize, int target, int* returnSize){
  7.     if(nums==NULL) return NULL;
  10.     int *res = (int*)malloc(sizeof(int)*2);
  11.     *returnSize = 2;
  13.     for(int i= 0;i<numsSize;i++) {
  16.         for(int j = i+1;j<numsSize;j++) {
  18.             if(nums[i] + nums[j] == target) {
  20.                 res[0] = i;
  21.                 res[1] = j;
  23.                 break;
  24.             }
  25.         }
  26.     }
  27.     return res;
  28. }

167.两数之和II-输入有序数组
题目：给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

  1. 输入: numbers = [2, 7, 11, 15], target = 9
  2. 输出: [1,2]
  3. 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
  5. int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
  9.     if(numbers==NULL) return NULL;
  12.     int *res = (int*)malloc(sizeof(int)*2);
  13.     *returnSize = 2;
  15.     for(int i= 0;i<numbersSize-1;i++) {
  18.         for(int j = i+1;j<numbersSize;j++) {
  20.             if(numbers[i] + numbers[j] == target) {
  22.                 res[0] = i+1;
  23.                 res[1] = j+1;
  25.                 break;
  26.             }
  27.         }
  28.     }
  29.     return res;
  30. }

对上述两个题目的总结：
题目区别：返回的下标是否从0开始
代码区别：
1

  1. res[0] = i;
  2.                 res[1] = j;

167

  1. res[0] = i+1;
  2.                 res[1] = j+1;

三数之和

15.三数之和
题目:给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

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

示例：

  1. 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
  3. 满足要求的三元组集合为：
  4. [
  5.   [-1, 0, 1],
  6.   [-1, -1, 2]
  7. ]

代码:

  1. //先将数组进行排序，然后进行三重循环。其中，前两重循环，使用普通遍历即可，需要做一下剪枝。
  2. //第三重循环，我这里用了二分查找（不用，或许也行），可以优化一下速度
  4. int cmp(const void *a, const void *b) 
  5. {
  7.     return *(int*)a - *(int*)b; // 比较大小
  8. }
  10. /**
  11.  * Return an array of arrays of size *returnSize.
  12.  * The sizes of the arrays are returned as *returnColumnSizes array.
  13.  * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
  14.  */
  15.  int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
  16. {
  18.     if (nums == NULL || returnSize == NULL || returnColumnSizes == NULL) {
  20.         return NULL;
  21.     } 
  22.     // 方便起见，先申请足够的内存
  23.     int max_count = numsSize * numsSize; // 认为足够了
  24.     int **p = (int **)malloc(sizeof(int*) * max_count); 
  25.     if (p == NULL) {
  26.      // 申请内存是否失败
  27.         return NULL;
  28.     }
  29.     *returnColumnSizes = (int*)malloc(sizeof(int) * max_count);
  30.     if (*returnColumnSizes == NULL) {
  31.      // 申请内存是否失败
  32.         free(p); // 释放之前申请的内存
  33.         return NULL;
  34.     }
  35.     memset(*returnColumnSizes, 0, sizeof(int) * max_count);
  36.     *returnSize = 0;
  37.     // 从小到大排序，时间复杂度O(nlogn)
  38.     qsort(nums, numsSize, sizeof(int), cmp);
  39.     /* for (int i = 0; i < numsSize; i++) {
  40.         printf("%d, ", nums[i]);
  41.     }
  42.     printf("\n"); */
  43.     for (int i = 0; i < numsSize; i++) {
  45.         if (nums[i] > 0) {
  46.      // 剪枝
  47.             continue;
  48.         }        
  49.         if (i > 0 && nums[i] == nums[i - 1]) {
  50.      // 剪枝
  51.             continue;
  52.         } 
  53.         for (int j = i + 1; j < numsSize; j++) {
  55.             if (nums[i] + nums[j] > 0) {
  56.      // 剪枝
  57.                 continue;
  58.             } 
  59.             if (j > i + 1 && nums[j] == nums[j - 1]) {
  60.      // 剪枝
  61.                 continue;
  62.             } 
  63.             // 这里用二分查找，进行优化
  64.             int left = j + 1;
  65.             int right = numsSize - 1;
  66.             while (left <= right) {
  68.                 int mid = (left + right) / 2;
  69.                 int sum = nums[i] + nums[j] + nums[mid];
  70.                 // printf("[%d]%d + [%d]%d + [%d]%d = (%d-%d)%d\n", 
  71.                 //      i, nums[i], j, nums[j], mid, nums[mid], left, right, sum);
  72.                 if (sum == 0) {
  73.      // 找到一个解
  74.                     p[*returnSize] = (int*)malloc(sizeof(int) * 3);
  75.                     if (p[*returnSize] == NULL) {
  77.                         return NULL;
  78.                     }
  79.                     p[*returnSize][0] = nums[i];
  80.                     p[*returnSize][1] = nums[j];
  81.                     p[*returnSize][2] = nums[mid];
  82.                     (*returnColumnSizes)[*returnSize] = 3;
  83.                     (*returnSize)++;
  84.                     break; // 找到则退出 
  85.                 } else if (sum > 0) {
  87.                     right = mid - 1;
  88.                 } else {
  90.                     left = mid + 1;
  91.                 }
  92.             }            
  93.         }
  94.     }
  95.     return p;
  96. }

疑惑：不清楚下面这样子为什么不可以
此处附上错误代码：

  1. /**
  2.  * Return an array of arrays of size *returnSize.
  3.  * The sizes of the arrays are returned as *returnColumnSizes array.
  4.  * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
  5.  */
  6. int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
  8.     if(nums==NULL)
  9.         return NULL;
  11.     int *res = (int*)malloc(3*sizeof(int));
  12.     *returnSize = 3;
  14.     int i,j,k;
  16.     for(i=0; i<numsSize-2; i++)
  17.     {
  19.         for(j=i+1; j<numsSize-1; j++)
  20.         {
  22.             for(k=j+1; k<numsSize; k++)
  23.             {
  25.                 if(nums[i]+nums[j]+nums[k]==0)
  26.                 {
  28.                     res[0]=i;
  29.                     res[1]=j;
  30.                     res[2]=k;
  31.                     break;
  32.                 }
  33.             }
  34.         }
  35.     }
  36.     return res;
  38. }

在这里插入图片描述
搜索了一下错误的原因:

  • LeetCode使用了AddressSanitizer检查了是否存在内存非法访问。
  • 在该题目中，是因为数组访问越界，也是绝大部分的内存访问题。

可是我不觉得自己for循环里有问题啊，如果大佬看到了错误或者有思路，愿闻详解，本菜鸟的荣幸

四数之和

18.四数之和
题目：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

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

示例：

  1. 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
  3. 满足要求的四元组集合为：
  4. [
  5.   [-1,  0, 0, 1],
  6.   [-2, -1, 1, 2],
  7.   [-2,  0, 0, 2]
  8. ]

发表评论

表情：
评论列表 （有 0 条评论，129人围观）

还没有评论，来说两句吧...

相关阅读

    相关 leetcode1. 两数之和js

    给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应

    梦里梦外;梦里梦外;/ 0 赞/ 276 阅读

    相关 两数之和LeetCode

    给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是

    男娘i男娘i/ 0 赞/ 391 阅读