题目描述
给定一个整数数组 nums 和一个目标值 target，请你在数组中找出和为目标值的那两个整数，并返回它们的下标。假设每种输入只会对应一个答案，且同样的元素不能被重复利用。
解题思路
为了解决这个问题，我们可以使用哈希表来提高查找的效率，可以将时间复杂度提升到O(1)。具体的解题思路如下：
- 遍历整数数组
nums，对于每个元素nums[i]，我们在哈希表中查找是否存在与target - nums[i]相等的元素。 - 如果存在，说明我们已经找到了两个数的和等于目标值，直接返回它们的下标。
- 如果不存在，将当前元素
nums[i]插入到哈希表中，以备后续查找。
解题代码
一、分解分析
1、定义哈希表的数据结构
struct hashTable { int key; // 键 int val; // 值 UT_hash_handle hh; // 用于表示哈希表的链表指针 };
在这里，我们定义了一个结构体 hashTable 来表示哈希表的元素。每个元素包含两个成员变量 key 和 val，分别表示键和值。UT_hash_handle hh 是一个宏，用于表示哈希表的链表指针。
关于UT_hash_handle hh
宏定义的相关详细描述如下：
HASH_FIND_INT(head, findint, out)：在哈希表中查找指定键的元素。head是哈希表的头指针，findint是要查找的键，out是用于接收查找结果的指针。HASH_ADD_INT(head, fieldname, add)：向哈希表中插入新的元素。head是哈希表的头指针，fieldname是哈希表中表示键的字段名，add是要插入的新元素。HASH_DEL(head, delptr)：从哈希表中删除指定的元素。head是哈希表的头指针，delptr是要删除的元素指针。HASH_ITER(hh, head, el, tmp)：用于遍历哈希表中的所有元素。hh是哈希表中用于表示链表的字段名，head是哈希表的头指针，el是当前遍历到的元素指针，tmp是临时指针。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，在哈希表中查找是否存在与当前元素匹配的元素，如果找到则返回它们的下标，如果没有找到则将当前元素插入到哈希表中。最后，如果没有找到符合条件的两个数，返回空指针。
希望我的题解对你有所帮助，感谢关注。
