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

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

[toc]

题目来源

如下图所示

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

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{

}

题目要求

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

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

题目要求如下：

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

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

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

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

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

实现步骤

1.模板中四个值的意义

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

1	int* twoSum(int* nums, int numsSize, int target, int* returnSize)

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

再来看题目的要求

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

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

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

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

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

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

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

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

for(int i = 0; i < numsSize - 1; i++)
 {
     for(int j = i+1; j < numsSize; j++)
     {
         
     }
 }

3.判断相加是否等于target

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

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

4.返回元素下标

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

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

创建这个数组有两种方法

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

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

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

代码示例1

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

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

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了这个数组，它也不能被主函数接收

static的作用

修饰函数
修饰全局变量
修饰局部变量

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

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

*returnSize是什么？

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

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

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

其实这里的*returnSize在main函数是有变量传过来的

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

1	*returnSize = 2;

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

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

代码示例2

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

什么是malloc函数？

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

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

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

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，空指针

malloc使用后free释放

在使用完malloc函数后

需要用free函数来释放malloc创建的内存空间
需要将创建的指针变量指向空指针，以防程序错误调用

1 2	free(pa); pa = NULL;

这两个函数是配对的

如果申请后不释放，会内存泄露
如果无故释放，那就是什么也没有做

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

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

/**
 * 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函数;

自己写代码的时候一定别忘了加哦！

初学总结

虽然这只是leetcode的第一题，网站打上的难度是“简单”

但对于我这个学艺不精的初学者来说，还是费了一番功夫去完成这道题并理解它

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

小声吐槽：csdn太多繁杂的东西了，有的博客代码不贴代码块，有的答案代码都是错的。
还有些人就这么一道题的答案都给你上传一个付费文件（无头像无id无简介，上传几千个资源，怀疑是机器人爬虫）

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

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

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

回顾

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

代码示例3

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

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

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

思路如下：

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

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

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;
    }   
};