用哈希函数实现两数之和的c语言代码
时间: 2024-05-29 15:11:09 浏览: 13
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10000
typedef struct Node {
int key;
int val;
struct Node* next;
} Node;
Node* createNode(int key, int val) {
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->val = val;
node->next = NULL;
return node;
}
void insert(Node** hashtable, int key, int val) {
int index = abs(key) % TABLE_SIZE;
Node* node = hashtable[index];
while (node != NULL) {
if (node->key == key) {
node->val = val;
return;
}
node = node->next;
}
Node* new_node = createNode(key, val);
new_node->next = hashtable[index];
hashtable[index] = new_node;
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
Node** hashtable = (Node**)malloc(sizeof(Node*) * TABLE_SIZE);
for (int i = 0; i < TABLE_SIZE; i++) {
hashtable[i] = NULL;
}
for (int i = 0; i < numsSize; i++) {
int complement = target - nums[i];
int index = abs(complement) % TABLE_SIZE;
Node* node = hashtable[index];
while (node != NULL) {
if (node->key == complement) {
int* result = (int*)malloc(sizeof(int) * 2);
result[0] = node->val;
result[1] = i;
*returnSize = 2;
return result;
}
node = node->next;
}
insert(hashtable, nums[i], i);
}
return NULL;
}
int main() {
int nums[] = {2, 7, 11, 15};
int target = 9;
int returnSize;
int* result = twoSum(nums, sizeof(nums) / sizeof(int), target, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
printf("\n");
return 0;
}