【C语言】Leetcode 两数之和 （含详细题解）

题目描述

        给定一个整数数组 nums 和一个目标值 target，请你在数组中找出和为目标值的那两个整数，并返回它们的下标。假设每种输入只会对应一个答案，且同样的元素不能被重复利用。

解题思路

为了解决这个问题，我们可以使用哈希表来提高查找的效率，可以将时间复杂度提升到O(1)。具体的解题思路如下：

1. 遍历整数数组 nums，对于每个元素 nums[i]，我们在哈希表中查找是否存在与 target - nums[i] 相等的元素。
2. 如果存在，说明我们已经找到了两个数的和等于目标值，直接返回它们的下标。
3. 如果不存在，将当前元素 nums[i] 插入到哈希表中，以备后续查找。

解题代码

一、分解分析

1、定义哈希表的数据结构

struct hashTable
{
    int key; // 键
    int val; // 值
    UT_hash_handle hh; // 用于表示哈希表的链表指针
};

         在这里，我们定义了一个结构体 hashTable 来表示哈希表的元素。每个元素包含两个成员变量 key 和 val，分别表示键和值。UT_hash_handle hh 是一个宏，用于表示哈希表的链表指针。

关于UT_hash_handle hh

        宏定义的相关详细描述如下：

1. HASH_FIND_INT(head, findint, out)：在哈希表中查找指定键的元素。head 是哈希表的头指针，findint 是要查找的键，out 是用于接收查找结果的指针。

2. HASH_ADD_INT(head, fieldname, add)：向哈希表中插入新的元素。head 是哈希表的头指针，fieldname 是哈希表中表示键的字段名，add 是要插入的新元素。

3. HASH_DEL(head, delptr)：从哈希表中删除指定的元素。head 是哈希表的头指针，delptr 是要删除的元素指针。

4. HASH_ITER(hh, head, el, tmp)：用于遍历哈希表中的所有元素。hh 是哈希表中用于表示链表的字段名，head 是哈希表的头指针，el 是当前遍历到的元素指针，tmp 是临时指针。

5. HASH_CLEAR(hh, head)：清空哈希表中的所有元素。hh 是哈希表中用于表示链表的字段名，head 是哈希表的头指针。

        这些宏使得对哈希表的操作变得非常简单，只需要调用相应的宏即可完成对哈希表的操作，而不需要手动编写复杂的链表操作代码。这样大大提高了代码的可读性和可维护性。

2、在哈希表中查找指定键的元素

struct hashTable* find(int ikey)
{
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp); // 使用宏来查找指定键的元素
    return tmp;
}

        这段代码定义了一个函数 find，用于在哈希表中查找指定键的元素。我们使用 HASH_FIND_INT 宏来实现查找操作。

 3、向哈希表中插入或更新元素

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; // 如果已经存在该键的元素，则更新其值
    }
}

         这段代码定义了一个函数 insert，用于向哈希表中插入或更新元素。首先，我们调用 find 函数来查找是否已经存在该键的元素。如果不存在，则创建新的元素并将其添加到哈希表中；如果已经存在该键的元素，则更新其值。

4、从给定的数组中找下标

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

         这段代码定义了一个函数 twoSum，用于从给定的数组中找到两个数的和等于给定目标值的下标。在函数中，我们首先初始化哈希表，然后遍历整数数组 nums。对于每个元素 nums[i]，我们在哈希表中查找是否存在与 target - nums[i] 相等的元素。如果存在，则返回它们的下标；如果不存在，则将当前元素插入到哈希表中。最后，如果没有找到符合条件的两个数，返回空指针。

二、整体代码题解（带详细注释）

// 定义哈希表的数据结构
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;
}

        在这段代码中，我们首先定义了哈希表的数据结构 struct hashTable，用 find 和 insert 函数来进行哈希表的查找和插入操作。然后，我们使用 twoSum 函数来解决题目要求的问题。该函数首先初始化哈希表，然后遍历整数数组 nums，在哈希表中查找是否存在与当前元素匹配的元素，如果找到则返回它们的下标，如果没有找到则将当前元素插入到哈希表中。最后，如果没有找到符合条件的两个数，返回空指针。

希望我的题解对你有所帮助，感谢关注。