两数之和哈希法c语言
时间: 2024-02-25 17:52:37 浏览: 22
下面是用哈希法实现两数之和的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 1000
typedef struct HashNode {
int key;
int value;
struct HashNode* next;
} HashNode;
typedef struct {
HashNode* data[HASH_SIZE];
} HashTable;
HashTable* createHashTable() {
HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));
for (int i = 0; i < HASH_SIZE; i++) {
hashTable->data[i] = NULL;
}
return hashTable;
}
void addNode(HashTable* hashTable, int key, int value) {
int hash = abs(key) % HASH_SIZE;
HashNode* node = hashTable->data[hash];
while (node != NULL) {
if (node->key == key) {
node->value = value;
return;
}
node = node->next;
}
HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = hashTable->data[hash];
hashTable->data[hash] = newNode;
}
int getValue(HashTable* hashTable, int key) {
int hash = abs(key) % HASH_SIZE;
HashNode* node = hashTable->data[hash];
while (node != NULL) {
if (node->key == key) {
return node->value;
}
node = node->next;
}
return -1;
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
HashTable* hashTable = createHashTable();
for (int i = 0; i < numsSize; i++) {
int complement = target - nums[i];
int index = getValue(hashTable, complement);
if (index != -1) {
int* result = (int*)malloc(sizeof(int) * 2);
result[0] = index;
result[1] = i;
*returnSize = 2;
return result;
}
addNode(hashTable, nums[i], i);
}
*returnSize = 0;
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]);
}
free(result);
return 0;
}
```
注:本代码实现了哈希表的基本操作,包括创建哈希表、添加节点、获取节点值。在实现twoSum函数时,我们利用哈希表记录每个元素在数组中的下标,然后在遍历数组的同时查找哈希表中是否存在与当前元素相加等于目标值的元素,如果存在就返回它们的下标。