一、前言

初次见面请多多关照，大家好，我是三水，一个大三在读的算法小白，今天是我刷leetcode算法的第四天啦！这是我第一次在平台上发表自己的文章，今后我也会持续地在平台上分享自己学习算法过程中的一些拙见和学习到的知识。希望友友们多加指正哈

二、两数相加

今天来做两数相加的算法题，我们先从理解题意和解题方式这两个部分展开来聊，上题！！！

1.题意

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

2.示例

输入：
nums = [2,7,11,15], target = 9
输出：
[0,1]
解释：
因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

3.题目解析

先分析题目重点：
明确输出的结果有两种情况，这里一定要看清楚啦！数组中同一元素在答案里是不能重复出现的，所以如果用暴力枚举法的话，那么我们在第二个for循环里面一定要从i+1开始

①如果能找到数组中两个下标不同的整数相加和为target，则返回这两个整数的数组下标；
②否则，为空

接下来跟大家来说说我第一眼看到这个题目的思路，哈哈，那必然是一上来就用暴力枚举解决（新手小白上线）
C语言代码实现：

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for(int i = 0; i < numsSize; i++)
    {
        for(int j = i + 1; j < numsSize; j++)
        {
            if(nums[i] + nums[j] == target)
            {
                int* ret = malloc(sizeof(int) * 2);
                ret[0] = i;
                ret[1] = j;
                *returnSize = 2;
                return ret;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

python代码实现：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        for i in range(n):
           for j in range(i + 1, n):
               if nums[i] + nums[j] == target:
                   return [i, j]
        return []

4.官方题解

官方题解提供了两种算法思路：暴力枚举；哈希表
接下来重点谈谈我对官方题解给出的使用哈希表算法解题的思路分析和代码分析：

思路分析

哈希表算法的优势：

暴力枚举法随着数据量的增大，查找速度也会不同程度地变慢，算法的时间复杂度和比较的次数是有关的，暴力枚举法的时间复杂度为O(n^2)，而使用哈希表来查找数组中是否存在目标元素，直接通过元素查找索引，这样时间复杂度会降低到O(1)，它的主要思想是通过将值和其存储位置相关联，来实现快速的随机存储。

思路及算法：

我们可以通过创建一个哈希表，对于每一个x，我们首先查询哈希表中是否存在target-x，然后再将x插入到哈希表中，即可保证不会让x和自己匹配（避免同一元素被使用两次）

代码分析

C语言代码实现及详细注释说明：

//自定义数据结构
struct hashTable {
    int key;//键
    int val;//值
    UT_hash_handle hh;//①使得自定义的数据结构可哈希
};

struct hashTable* hashtable;//定义哈希表指针，这个指针为前面自定义数据结构的指针
//根据key值查找节点
struct hashTable* find(int ikey) {
    struct hashTable* tmp;//定义hashTable结构体指针变量tmp
    HASH_FIND_INT(hashtable, &ikey, tmp);//②找到ikey所对应的hash结构体
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);//返回ikey值对应的节点it
    if (it == NULL) {//如果没有找到，就添加
        struct hashTable* tmp = malloc(sizeof(struct hashTable));//③为tmp申请内存空间
        tmp->key = ikey, tmp->val = ival;//将结构体变量tmp的值指向ikey，键指向ival
        HASH_ADD_INT(hashtable, key, tmp);//④向hashtable添加元素
    } else {//如果找到，就替换
        it->val = ival;//将在it的值指向替换为ival
    }
}
//两数相加功能实现函数
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;//初始化hashtable为空
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);//查找key = target - nums[i]对应的节点
        //⑤if……else……内部逻辑关系没有理解透
        if (it != NULL) {//如果找到
            int* ret = malloc(sizeof(int) * 2);//为ret申请空间
            ret[0] = it->val, ret[1] = i;//ret[0]为target-nums[i]对应的元素下标，ret[1]即为nums[i]对应元素下标
            *returnSize = 2;//设置返回的数组长度为2
            return ret;//返回两元素的下标
        }
        insert(nums[i], i);//如果没有找到就将nums[i]插入到哈希表中
    }
    *returnSize = 0;//遍历完成后，在哈希表中仍然没有找到匹配元素，则设置返回的数组长度为0
    return NULL;//返回空
}

python代码实现及详细注释说明：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashtable = dict()#创建一个空字典hashtable
        for i, num in enumerate(nums):#序列解包，遍历索引值以及对应的元素值
            if target - num in hashtable:#如果target-num存在于字典的键值中
                return [hashtable[target - num], i]#返回两元素对应的下标
            hashtable[nums[i]] = i#如果target-nums[i]尚且不存在于字典hashtable的键值中，则将nums[i]:i添加到hashtable字典中
        return []#遍历完成后，仍然没有在字典中找到对应两个元素相加之和为target，则返回空

三、重难点解析

1.在自定义结构体中定义UT_hash_handle类型变量的作用

（1）uthash是一个C语言的hash表实现，它是以宏定义的方式去实现hash表的，这样不仅加快了运行的速度，而且还与关键类型无关。uthash使用起来也非常方便，只需要将头文件uthash.h包含进去就能使用。
（2）UT_hash_handle是用户自定义数据必须包含的结构，每一个用户自定义的节点都必须要包含一个UT_hash_handle hh。
（3）UT_hash_handle hh：hh是内部使用的hash处理句柄，在使用过程中，只需要在自定义的结构体中定义一个UT_hash_handle类型的变量即可，变量名的名称可以任意取，但是我们一般都会使用hh（敲黑板：不需要为该句柄变量赋值，但是必须要在该结构体中定义该变量）

2.malloc()申请内存空间注意事项

（1）malloc()可用于动态分配内存空间，malloc(size_t size)函数内有一个参数，即要分配的内存空间的大小。
（2）malloc()默认的类型为（void *），（void *）表示的是返回的指针类型未知，而不是说没有返回值或者返回空指针。任何类型的指针都可以转换为（void *），但是保险起见最好还是进行强制类型转换。
（3）malloc()只负责开辟空间，不能初始化所分配的内存空间，在动态分配完内存后，里面的数据是随机的垃圾数据。
（4）malloc()的返回值是一个对象。
（5）申请内存空间后，必须检查是否分配成功。当不再需要申请的内存空间后，记得使用free()释放，另外释放后，应该将指向这块内存的指针指向NULL，防止后面不小心被程序使用。
（6）malloc()和calloc()的区别：
①初始化内存空间：malloc()仅负责开辟空间，calloc()会将开辟的空间初始化为0
②参数个数：malloc(size_t size)函数有一个参数，既要分配的内存空间的大小；calloc(size_t numElements, size_t sizeOfElement)有两个参数，分别是元素的数目和元素的大小
③函数返回值：malloc()返回对象，calloc()返回数组
④效率：malloc()比calloc()更高效

3.HASH_FIND

（1）根据key值数据类型的不同，我们使用不同类型的接口找到key值所对应的hash结构体，常见的有：Uthash为整型key提供的查找接口为HASH_FIND_INT；为字符型key提供的查找接口为HASH_FIND_STR……
（2）HASH_FIND_INT(hashtable, &key, s)：第一个参数hashtable表示自定义的哈希表指针，第二个参数表示键值key的地址，第三个s是输出的结构体指针变量。
（3）该函数的返回值：当在哈希表hashtable中找到对应的键值时，s返回给定键的结构，当找不到对应的键值时，返回NULL。

4.HASH_ADD

（1）根据添加的key值数据类型的不同，我们使用不同类型的接口，常见的有：HASH_ADD_INT表示添加的键值为int类型，HASH_ADD_STR表示添加的键值为字符型，HASH_ADD_PTR表示添加的键值为指针类型，HASH_ADD表示添加的键值可以是任意类型的。
（2）HASH_ADD_INT(hashtable, key, s)：第一个参数hashtable表示自定义的哈希表指针，第二个参数表示key的名称，第三个s是指向要添加的结构体指针变量。

5.理解两数相加函数中关于是否在哈希表中查找到对应元素的算法思路

if (it != NULL) //如果找到
{
int* ret = malloc(sizeof(int) * 2);//为ret申请空间
//ret[0]为target-nums[i]对应的元素下标，ret[1]即为nums[i]对应元素下标
ret[0] = it->val, ret[1] = i;
*returnSize = 2;//设置返回的数组长度为2
return ret;//返回两元素的下标
}
insert(nums[i], i);//如果没有找到就将nums[i]插入到哈希表中

如果在哈希表中查找到了target-nums[i]对应的节点，则返回target-nums[i]的value值和i，否则就将nums[i]添加到哈希表中，这样就能有效避免重复遍历到同一元素。

四、总结

通过对力扣上“两数相加”这道题的分析总结过后，自己对哈希表的理解更加深入，今后在针对这一类键值对问题我也多了一种求解方法——哈希表，虽然说暴力求解固然也是一种办法，但学习之路不能停滞不前，我们需要寻求一道问题的不同解法来扩展自己的知识面，尽量做到一题多解。
这是我在CSDN上发布的第一篇文章，也见证了我刚刚起步的leetcode刷题之旅，希望看到这篇文章的友友们能陪伴我一起成长！！！咱们一起加油！
请添加图片描述
参考链接1: C语言哈希表的使用.
参考链接2: Uthash的用法.