这是初学C时候写的题解，可能有思维漏洞，后面重新刷题的时候会更改！

PS：已重新更正并添加了C++的哈希解法

[toc]

1 题目来源

两数之和 leetcode-001

如下图所示

image-20211031134426182

右侧给出了题目的基本模板

1
2
3
4
5
6
7
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{

}

2 题目要求

做题之前，我们需要梳理出题目的各项要求

算法题目需要我们非常细致，因为一个小要求的未完成，就会导致格式出问题或者结果出问题，无法通过系统的测试

题目要求如下：

  • 在给定数组nums中找出相加为target的两个数字
  • 同一个数字不能重复
  • 假设每一个target只对应一种答案
  • 找到数字后返回元素的下标
  • 不能更改摸板里的代码

这里还有一个容易被忽略的隐藏条件！

  • 相加的两个数字在数组中是连续的

这个条件是观察3个示例得出的，如果没有这个条件，这道题目就需要我们在数组中进行完全搜索！

我做这道题目的时候就卡在了这个地方！

3 实现步骤

3.1 模板中四个值的意义

首先我们要弄明白摸板里的4个值分别代表什么东西

1
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
  • int* nums——nums数组（ 此形式等同于int nums[] )
  • numsSize——数组元素的个数
  • target——需要求和的结果
  • int* returnSize——返回值的个数（这个不可以省略！）

再来看题目的要求

需要在给定数组中找到相加=target的两个连续的数字

3.2 在数组中找到两个连续的元素

一般在数组里面查找一个数字，我们都会想到使用for循环

这里需要查找两个连续的数字，可以使用两个嵌套的for循环以及两个循环变量来实现

更新：实际上这两个数字不一定是连续的，用双循环的暴力写法，非连续数字其实也是能搞定的

1
2
int i=0；
int j=i+1;

需要注意的是，j比i大了1，为了防止数组越界访问

for循环里面的判断变量也要相应的差1

1
2
3
4
5
6
7
for(int i = 0; i < numsSize - 1; i++)
 {
     for(int j = i+1; j < numsSize; j++)
     {
         
     }
 }

3.3 判断相加是否等于target

在数组中找到元素后，需要判断它们两个相加是否等于target

1
if(nums[i] + nums[j] == target)

3.4 返回元素下标

当代码成功找到了两个相加等于target的元素后，我们要返回这两个元素的下标

这里就需要一个新的数组来接收这两个下标，这比单纯的使用两个变量更方便

创建这个数组有两种方法

  1. 使用arr[2]来创建
  2. 使用malloc函数来创建

其中方法二，是题目所给提示里的函数，后续将提及

1
/* Note: The returned array must be malloced, assume caller calls free(). */

4 代码示例1

注：leetcode的函数题目只需要补全自定义函数，无需写main函数

在示例1里面，使用普通的方式创建result[2]数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int* twoSum(int* nums, int numsSize, int target,int* returnSize) 
{
    static int result[2] = {0};//static修饰后，return的地址才能被main接收
    for(int i = 0; i < numsSize - 1; i++)
    {
        for(int j = i+1; j < numsSize; j++)
        {
            if(nums[i] + nums[j] == target)
            {
                result[0] = i;
                result[1] = j;
                *returnSize = 2;//这个不能删除
                return result;
            }
        }
    }
    return NULL;
}

因为我们需要在main函数里面使用result数组的值，所以需要用static来修饰这个数组

不用static修饰的话，出了自定义函数后，result数组的内存空间将被释放

即便我们return了这个数组，它也不能被主函数接收

4.1 static的作用

  1. 修饰函数
  2. 修饰全局变量
  3. 修饰局部变量

这里使用的是static的第3个作用，将局部变量数组result，变成静态局部变量

即数组result不会在出自定义函数后销毁

4.2 *returnSize是什么？

屏幕前的你是否和我有一样的疑惑，此*returnSize在自定义函数里面没有意义。那为什么不能删除？

要知道，这里的*returnSize是题目的模板给我们的

而且题目没有要求我们书写main函数

其实这里的*returnSize在main函数是有变量传过来的，我们需要将它作为一个输出参数进行赋值。

删除这个参数后，自定义函数里缺少变量来接受传过来的数据，自然会报错

1
*returnSize = 2;

同时，我们需要在if语句中将它定义为2，即为返回值的个数。

具体的分析参考这篇博客==> 链接

5 代码示例2

说第二种方法前，我们必须先弄明白malloc函数是什么

5.1 什么是malloc函数？

在cplusplus网站，我们可以查看到malloc函数的定义

该函数对应的头文件为cstdlib，即c语言中的<stdlib.h>

image-20211031154520812

它的作用，简单来说就是在内存中开辟对应字节的空间，赋予给一个指针变量

1
int *pa = malloc(sizeof(int));

上面这个语句的意义是，开辟一个int类型（即4个字节）的空间，赋给指针变量*pa

其中的sizeof(int)可以换成(4)；也可以在后面乘上一个数sizeof(int)*2表示8个字节

本题需要的是存放两个int整形的数组，malloc函数可以这么写

1
int *num = malloc(sizeof(int)*2);

cplusplus对malloc函数中的定义里有一句话

If the function failed to allocate the requested block of memory, a null pointer is returned.

如果指针分配错误，函数将返回一个NULL，空指针

5.2 malloc使用后free释放

在使用完malloc函数后

  • 需要用free函数来释放malloc创建的内存空间
  • 需要将创建的指针变量指向空指针，以防程序错误调用
1
2
free(pa);
pa = NULL;

这两个函数是配对的

  • 如果申请后不释放，会内存泄露

  • 如果无故释放，那就是什么也没有做

内存泄漏参考这篇博客 ==> 链接；

以下就是方法2的完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    int *num = malloc(sizeof(int)*2);
    for(int i = 0; i < numsSize - 1; i++)
    {
        for(int j = i + 1; j < numsSize; j++)
        {
            if(nums[i] + nums[j] == target)
            {
                num[0] = i;
                num[1] = j;
                *returnSize = 2;
                return num;
            }
        }
    }
    return NULL;
}

为什么本题使用完malloc函数后没有free呢？

原因还是在本题的提示里

1
/*Note: The returned array must be malloced, assume caller calls free()*/

这个语句的大概意思应该是：假设main函数里面已有一个free函数来释放内存；

所以我们不需要自己加上free函数; 自己写这种类型的代码的时候一定别忘了加哦！

6 初学总结

虽然这只是leetcode的第一题，网站打上的难度是“简单”，但对于我这个学艺不精的初学者来说，还是费了一番功夫去完成这道题并理解它。

本片博客就是我求解这道题的过程，希望对你有帮助！

小声吐槽：csdn太多繁杂的东西了，有的博客代码不贴代码块，有的答案代码都是错的。

还有些人就这么一道题的答案都给你上传一个付费文件（无头像无id无简介，上传几千个资源，怀疑是机器人爬虫）

不管怎么样，至少我弄懂这道题啦！

感谢引用的两篇博客的作者，若不是他们，我也弄不明白这道题！

点个👍再走吧，球球了！这对我真的很重要啊！

7 回顾

已经是2023年的2月份了，距离我写下这篇文，已经过去了一年多的时光。回顾看来，当时写的教程着实不太好，于是返回来更正一番

7.1 代码示例3

此题最佳的解决方案是哈希思想。哈希就是一个映射关系。

如果你不知道什么是哈希，建议暂时先采用上面的双循环暴力解法。等后续学习了哈希思想以及实现之后，再回头来重做此题

我们可以将数组中的数据和其对应的下标插入到哈希表中，由于哈希表的搜索效率接近O(1)，查找的速度是很快的，此题的整体时间复杂度就变成了O(N)

思路如下：

  • 查找哈希表中，是否有和（目标-当前值）相同的元素
  • 如果有，那么得到答案。返回当前遍历到的下标，以及查找到的元素的下标
  • 如果没有，那就把当前元素-元素下标作为键值对，插入到哈希表中

因为本题是一定有解的，这样一次循环之后，一定能找到我们需要的那两个数的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;//哈希表 数据-下标
        vector<int> ret;//返回值
        for(int i=0;i<nums.size();i++)
        {
	        //找有没有和（目标-当前值）相同的元素
            auto it = m.find(target-nums[i]);
            if(it!=m.end())//找到了
            {
                ret.push_back(it->second);//插入哈希表中下标
                ret.push_back(i);//插入当前下标
                break;//退出循环
            }
            else
            {
                m.insert({nums[i],i});//插入元素和下标
            }
        }
        return ret;
    }   
};

image-20230201184859839