力扣（Leetcode）第1题：两数之和（C语言版本）_力扣 两数之和c语言

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

力扣官方题目

例题

解题

方法一：暴力解法（时间复杂度高）

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* array = (int *)malloc(2*sizeof(int));//定义一个指针，为了防止其指针为野指针，使用malloc开辟对应的空间
    //使用for循环遍历整个数组
    for(int i = 0;i<numsSize;i++){
        for(int j=i+1;j<numsSize;j++){
        	//if((*(nums+i))+(*(nums+j)) == target) 也正确
            if(nums[i]+nums[j] == target){//判断是否等于目标值
                array[0] = i;
                array[1] = j;
                *returnSize = 2;//标志返回东西的个数而已，没有其他意思
                return array;//返回地址
            }
        }
    }
    //若未找到目标值
    *returnSize = 0;
    array = NULL;//空指针
    return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

疑问解答

1. 为什么需要定义int *array?

– because ：在题目中给出定义好的指针函数（int* int* twoSum），所以需要有返回值且返回值必须是地址，那么我们使用指针来返回地址。

2. 为什么int* array = (int )malloc(2sizeof(int))，中需要2×sizeof(int)?

– because : 题目需要返回两个数组下标值，所以需要两个int大小，malloc()函数为开辟空间函数，为了给定义的int* array开辟空间，防止其成为野指针，而（int*）是起到强转的目的。

方法二：哈希表法（时间复杂度低）

对于哈希表法原理可查看视频：
哈希表法1-bilibili
哈希表法2-bilibili
上面两个up主讲的都是很不错滴！！！
以下是我的讲解，若有不理解的地方，请看上述视频，自己能力有限（也是初学者）。

哈希表法的大概意思就是如此，若是还是未懂，那么请看上面的两个视频，动动自己的小手，点击查看以下，优质up主！！！

struct HashTable//定义哈希表结构体
{
    int key;// 元素值
    int val;// 索引值
    UT_hash_handle hh;// 下一个专题来解答
};

struct HashTable* hashtable;// 定义结构体指针（跟我们平常定义指针一样滴）--定义哈希表
//（stuct HashTable* 等同于int *  这只是说明该指针为什么类型的而已）

struct HashTable* find(int ikey)//定义函数指针--为了寻找对应元素的索引值
{
	//因为该函数为指针函数，返回一个地址，那么我们可以用指针来操作
    struct HashTable* tmp;//缓冲器--只是把相应的地址放入到这，并返回该数据
    HASH_FIND_INT(hashtable,&ikey,tmp);//下一个专题来解答（宏）
    return tmp;//返回地址（因为该函数为指针函数，需要返回一个地址）
}

void insert(int ikey,int ival)//插入哈希表操作
{
    struct HashTable* it = find(ikey);//根据元素值，寻找索引值，并把地址赋给it
    if(it == NULL)//若哈希表中无该元素
    {
    	//添加到哈希表中
        struct HashTable* tmp = malloc(sizeof(struct HashTable));//给缓冲区开辟相应的空间大小
        tmp -> key = ikey;//元素值赋值
        tmp -> val = ival;//索引值赋值
        HASH_ADD_INT(hashtable,key,tmp);//下一个专题来解答（宏）
    }else{//若在哈希表中发现该元素
        it -> val = ival;//更换索引值
    }
}
//从此处开始看！！！find()和insert()函数都是上面定义的
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;//初始化，先使哈希表内部为空（NULL）
    for(int i = 0;i < numsSize;i++){//遍历数组
        struct HashTable* it = find(target-nums[i]);//寻找目标值
        if(it != NULL){//若哈希表中存在该元素，则it不为NULL,执行下面程序
            int* ret = malloc(sizeof(int) * 2);//定义指针并开辟对应大小的空间
            ret[0] = it -> val;//把哈希表中的目标值的索引值返回
            ret[1] = i;//把正在遍历到的数组元素的索引值返回
            *returnSize = 2;//返回数据的个数
            return ret;//返回地址（ret的下面的两个地址所存放的元素已经更改）
        }
        insert(nums[i],i);//若哈希表中无正在遍历的数组元素，则把该数组元素插入哈希表中
    }
    *returnSize = 0;
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

这段代码为官方给的解答，当然是不唯一的！力扣官方哈希表法源代码
若是第一次接触发现，心中大概率会默默的想，哎我去，这啥啊，看不懂啊！！！
莫问题的啦！！！ 我来一点一点解释（只要接触过C语言指针滴），若是还是有不懂的地方，那么大家可以评论或者私信我，只要我看到了一定会回滴！！！

疑问解答

1. 这段代码与视频中讲解的不太一样呀?

– because : 好问题，我在学习的时候也是比较懵的，感觉跟讲的不一样哎！！！
视频中和我上述讲解的是把数组各个元素的元素先放入了哈希表中了，之后在遍历数组并查询哈希表。but : 要是真的完全这样操作，是不是得遍历两遍数组表呀，是不是有点费时间呀（当然比暴力法节省很多时间）。
在代码中采用的是，先把哈希表清空，只有随着遍历数组元素的同时也在向哈希表中添加元素，这样是比较节省时间的，有可能在没有遍历完整个数组元素已经找到了目标值了。那么我用下图来解释一下吧！




上图就是该程序的运行流程，希望各位能看懂，若有哪块没看到，十分期待各位询问腻！！！

2. UT_hash_handle hh 是什么？

– because : 是一个用于实现哈希表功能的关键成员，它使得 struct HashTable 可以作为一个有效的哈希表元素，支持高效的键值查找、插入和删除操作。这些功能通过使用第三方库提供的宏（如 HASH_FIND_INT 和 HASH_ADD_INT）来间接访问和操作 UT_hash_handle 成员实现。（hh 名字随意更换！！！）

3. HASH_FIND_INT(hashtable,&ikey,tmp)是什么？

– because : 是在哈希表 hashtable 中查找键值为 ikey 的元素，如果找到，则将找到的元素的指针赋给 tmp，否则将 tmp 设为 NULL。这样，通过检查 tmp 是否为 NULL，就可以判断查找是否成功。

4. HASH_ADD_INT(hashtable,key,tmp)是什么？

– because : 在哈希表 hashtable 中添加或更新一个由 tmp 指向的 struct HashTable 类型的元素。
key 参数指定了用于哈希表操作的键字段名，即结构体中的 int key。这个参数告诉宏应该使用哪个字段作为元素的唯一标识符（键），以便在哈希表中进行相应的插入或更新操作。