文章目录

• 前言
• 一、题目
• 二、答案（一遍hash的代码）
• • 1.在看代码前需要知道的库

---

前言

  在学习c的时候，想着用刷题的思路学习，所以从LeetCode的题库中最简单的“两数之和”开始，然后把每一道题的所有知识点都搞明白，这是第一题。我会把所有的从最基础的开始讲明白，记录自己的成长。

---

一、题目

给定一个整数数组 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]

提示:

• 2 <= nums.length <= 104
• 109 <= nums[i] <= 109
• 109 <= target <= 109
• 只会存在一个有效答案
  进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

二、答案（一遍hash的代码）

  由于我是根据结果学习，所有是直接从代码反过来推如何解这个问题的。

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

//查找
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);
    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;
    }
}

//求和
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) {
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it->val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

1.在看代码前需要知道的库<uthash.h>

  这个库是一个开源的库，主要是实现哈希算法的一些功能，官方文档如下：

Any C structure can be stored in a hash table using uthash. Just add a UT_hash_handle to the structure and choose one or more fields in your structure to act as the key. Then use these macros to store, retrieve or delete items from the hash table.
任何 C 结构都可以使用 uthash 存储在哈希表中。 只需在结构中添加一个 UT_hash_handle 并在您的结构中选择一个或多个字段作为键。 然后使用这些宏来存储、检索或删除哈希表中的项目。

具体的可以去看《开源库uthash第一弹uthash.h》我就是看的这篇。

2.代码解释

 1.声明结构体hashTable

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

这段代码定义了一个叫做hashTable的结构体声明了2个int类型的变量，从名字来看：
key是哈希表的键。
val是值。
hh是内部使用的hash处理句柄，在使用过程中，只需要在结构体中定义一个。UT_hash_handle类型的变量即可，不需要为该句柄变量赋值，但必须在该结构体中定义该变量；
Uthash.h这个库所实现的hash表中可以提供类似于双向链表的操作，可以通过结构体成员hh的hh.prev和hh.next获取当前节点的上一个节点或者下一个节点。

注意：在uthash中，当您的结构添加到hash表中时，并不会被移动或拷贝到其他位置。这意味着在程序运行过程中，无论是对hash表进行添加或删除操作，都可以保证您数据结构的安全性。
 下面是uthash.h库中定义UT_hash_handle的源码。

struct UT_hash_handle {
   struct UT_hash_table *tbl;
   void *prev;                       /* prev element in app order      */
   void *next;                       /* next element in app order      */
   struct UT_hash_handle *hh_prev;   /* previous hh in bucket order    */
   struct UT_hash_handle *hh_next;   /* next hh in bucket order        */
   const void *key;                  /* ptr to enclosing struct's key  */
   unsigned keylen;                  /* enclosing struct's key len     */
   unsigned hashv;                   /* result of hash-fcn(key)        */
} UT_hash_handle;

 2.声明指针hashtable

struct hashTable* hashtable;

声明一个结构体hashTable类型的名叫hashtable的指针。这个指针只能指向hashTable类型数据的地址。

 3.声明函数find

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

声明了一个返回值为hashTable类型指针的函数find，find函数的返回值是一个指针且该指针只能是指向hashTable类型，使用返回值其实是一个地址。
这个find函数重要的是其调用的HASH_FIND_INT这个函数。
作用：顾名思义这个HASH_FIND_INT函数是用来查找哈希表中int类型的哈希值是否存在，存在就返回对应输入键值的结构，当找不到时返回NULL。通过tmp这个结构体指针返回。
用法：参数1：哈希表；参数2：要查找的键值的地址；参数3：哈希表结构的结构体指针。
知道了关键函数的用法和作用，那么这个find函数的作用就很简单了，既输入一个键值，哈希表中有则返回对应键的结构体，没有就返回NULL。（之所以没贴源码是内容很多，放一张我自己看源码是画的的一个思维导图）
一个函数由6个函数堆起来所以看起来会比较麻烦，而且这个库是用宏写的所以不太好理解。

 4.声明函数insert

//插入
void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    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函数一样，最重要的是 HASH_ADD_INT函数，这个函数和上面的一样，通过名字看用法，就是将对应的键值和数值添加到哈希表中。
作用：将输入的键值添加到哈希表中去。
用法：参数1：哈希表；参数2：键值；参数3：对应的结构体指针。
“->”箭头符号的意思和“.”差不多，可以看成成员符，tmp->key等价于tmp.key。
整个函数的作用是：
1. 先查重，看哈希表中是否存在对应的键值，若存在就会修改哈希表如下：
假设哈希表中有如下内容：

key	2	4	6	8	10	12
val	1	2	3	4	5	6

此时调用find函数传入一个key值，如：6
此时哈希表中有该键值，因此返回一个结构体结构体的值如下：

it {
    int &key=6;
    int &val=3;
    UT_hash_handle hh;
};

然后执行

it->val = ival;

此时哈希表为：

key	2	4	6	8	10	12
val	1	2	7	4	5	6

当原本哈希表中没有时就会正常的在后面添加，假如键值是14，那么哈希表应该是下面的样子

key	2	4	6	8	10	12	14
val	1	2	3	4	5	6	7

2.判断find返回值，返回值为NULL时，定义一个哈希表指针，并给这个指针分配一个内存空间大小为哈希表结构体的大小。返回值为其他时就是改变哈希表的结构，具体参考上文的描述。
3.将键值和数值赋给哈希表指针的对应成员。
4.调用 HASH_ADD_INT函数将其加入到哈希表中去。

5.目标的求和函数twoSum

//求和
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) {
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it->val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

1.首先将哈希表hashtable赋值为NULL，首先要使用指针必须要赋值，其次要要确保指针中没有除了你要放进去的数据以外的东西，因此必须赋值为NULL。
2.接下来的for循环相信都能明白，就是循环数组大小的次数。
3.声明一个结构体指针并赋值为find函数的返回值，这个可以结合上面的find函数来看。
4.用if判断指针it是否为NULL，也是去看find函数，如果不为NULL说明已经找到目标数组，此时retrun对应的下标；如果为NULL就执行下面的 insert(nums[i], i)语句，将对应的键值和数值插入哈希表中。
5.*returnSize返回值的大小。

总结

以上就是本文要讲的内容，本文简单的介绍了leetcode的经典题目，两数之和的C语言版的：一遍哈希表法。希望能对大家有所帮助。