两数之和：哈希表高效解法，时间复杂度O(n)

<｜begin▁of▁sentence｜># 1. 两数之和 ## 题目 给定一个整数数组 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) 的算法吗？ ## 解题思路 最直接的思路是暴力枚举，遍历数组中的每一个元素x，然后寻找数组中是否存在另一个元素y，使得x + y = target。但是这样的时间复杂度是O(n^2)，空间复杂度是O(1)。 为了降低时间复杂度，我们可以使用哈希表。具体来说，我们可以创建一个哈希表，对于数组中的每一个元素x，我们首先查询哈希表中是否存在target - x，如果存在，那么我们就找到了对应的两个元素，返回它们的下标；如果不存在，那么我们就将x插入到哈希表中，这样在后续的遍历中，如果遇到target - x，就可以直接找到x。 这种方法的时间复杂度是O(n)，因为哈希表的查找和插入操作的时间复杂度都是O(1)。空间复杂度是O(n)，因为我们需要存储数组中的元素和它们的下标。 ## 代码 ```c #include #include typedef struct { int key; int value; int used; } HashEntry; typedef struct { HashEntry *entries; int size; } HashTable; HashTable* createHashTable(int size) { HashTable *ht = (HashTable *)malloc(sizeof(HashTable)); ht->size = size; ht->entries = (HashEntry *)calloc(size, sizeof(HashEntry)); for (int i = 0; i < size; i++) { ht->entries[i].used = 0; } return ht; } void freeHashTable(HashTable *ht) { free(ht->entries); free(ht); } int hash(int key, int size) { return abs(key) % size; } void insert(HashTable *ht, int key, int value) { int index = hash(key, ht->size); while (ht->entries[index].used) { index = (index + 1) % ht->size; } ht->entries[index].key = key; ht->entries[index].value = value; ht->entries[index].used = 1; } int search(HashTable *ht, int key) { int index = hash(key, ht->size); while (ht->entries[index].used) { if (ht->entries[index].key == key) { return ht->entries[index].value; } index = (index + 1) % ht->size; } return -1; } int* twoSum(int* nums, int numsSize, int target, int* returnSize) { HashTable *ht = createHashTable(numsSize * 2); int *result = (int *)malloc(2 * sizeof(int)); *returnSize = 2; for (int i = 0; i < numsSize; i++) { int complement = target - nums[i]; int index = search(ht, complement); if (index != -1) { result[0] = index; result[1] = i; freeHashTable(ht); return result; } insert(ht, nums[i], i); } freeHashTable(ht); return result; } int main() { int nums[] = {2, 7, 11, 15}; int target = 9; int returnSize; int *result = twoSum(nums, 4, target, &returnSize); printf("[%d, %d]\n", result[0], result[1]); free(result); return 0; } ``` ## 复杂度分析 时间复杂度：O(n)，其中n是数组中的元素数量。对于每一个元素x，我们可以O(1)地寻找target - x。 空间复杂度：O(n)，其中n是数组中的元素数量。主要为哈希表的开销。 ## 结果 执行结果：通过 执行用时：56 ms 内存消耗：7.1 MB ## 总结 通过使用哈希表，我们可以将时间复杂度从O(n^2)降低到O(n)，虽然增加了空间复杂度，但在大多数情况下，这是一种值得的权衡。