用c语言哈希表法实现two sums完整代码
时间: 2023-10-11 19:05:31 浏览: 49
下面是用C语言哈希表法实现two sums的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 1009
typedef struct ListNode {
int val;
int index;
struct ListNode *next;
} ListNode;
ListNode *hashTable[HASH_SIZE];
void insert(int key, int index) {
int h = abs(key) % HASH_SIZE;
ListNode *node = hashTable[h];
while (node != NULL) {
if (node->val == key) {
return;
}
node = node->next;
}
ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
newNode->val = key;
newNode->index = index;
newNode->next = hashTable[h];
hashTable[h] = newNode;
}
int *twoSum(int *nums, int numsSize, int target) {
for (int i = 0; i < HASH_SIZE; i++) {
hashTable[i] = NULL;
}
for (int i = 0; i < numsSize; i++) {
insert(nums[i], i);
}
int *result = (int *)malloc(2 * sizeof(int));
for (int i = 0; i < numsSize; i++) {
int complement = target - nums[i];
int h = abs(complement) % HASH_SIZE;
ListNode *node = hashTable[h];
while (node != NULL) {
if (node->val == complement && node->index != i) {
result[0] = i;
result[1] = node->index;
return result;
}
node = node->next;
}
}
return NULL;
}
int main() {
int nums[] = {2, 7, 11, 15};
int target = 9;
int *result = twoSum(nums, sizeof(nums) / sizeof(int), target);
printf("[%d, %d]\n", result[0], result[1]);
free(result);
return 0;
}
```
代码中使用了链表来实现哈希表,哈希表大小为1009(一个质数),插入和查找的时间复杂度均为$O(1)$。在函数`twoSum`中,首先将所有数插入哈希表,然后遍历数组,对于每个数,计算它的补数,查找补数是否存在于哈希表中。如果存在,返回它们的下标即可。在函数结束时,需要释放动态分配的结果数组。