哈希表两数之和c++

你可以使用哈希表来解决两数之和的问题。哈希表是一种将键和值进行映射的数据结构，它可以快速地查找给定键对应的值。以下是一个使用哈希表求解两数之和的示例代码：

#include <stdio.h>
#include <stdbool.h>

typedef struct {
    int key;
    int value;
} HashNode;

typedef struct {
    HashNode** table;
    int size;
} HashMap;

HashMap* createHashMap(int size) {
    HashMap* hashMap = (HashMap*)malloc(sizeof(HashMap));
    hashMap->size = size;
    hashMap->table = (HashNode**)malloc(sizeof(HashNode*) * size);
    for (int i = 0; i < size; i++) {
        hashMap->table[i] = NULL;
    }
    return hashMap;
}

void put(HashMap* hashMap, int key, int value) {
    int hash = abs(key) % hashMap->size;
    while (hashMap->table[hash] != NULL && hashMap->table[hash]->key != key) {
        hash = (hash + 1) % hashMap->size;
    }
    if (hashMap->table[hash] != NULL) {
        free(hashMap->table[hash]);
    }
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->value = value;
    hashMap->table[hash] = node;
}

int get(HashMap* hashMap, int key) {
    int hash = abs(key) % hashMap->size;
    while (hashMap->table[hash] != NULL && hashMap->table[hash]->key != key) {
        hash = (hash + 1) % hashMap->size;
    }
    if (hashMap->table[hash] == NULL) {
        return -1;
    } else {
        return hashMap->table[hash]->value;
    }
}

bool containsKey(HashMap* hashMap, int key) {
    int hash = abs(key) % hashMap->size;
    while (hashMap->table[hash] != NULL && hashMap->table[hash]->key != key) {
        hash = (hash + 1) % hashMap->size;
    }
    return hashMap->table[hash] != NULL;
}

void freeHashMap(HashMap* hashMap) {
    for (int i = 0; i < hashMap->size; i++) {
        if (hashMap->table[i] != NULL) {
            free(hashMap->table[i]);
        }
    }
    free(hashMap->table);
    free(hashMap);
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    HashMap* hashMap = createHashMap(numsSize);
    
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        if (containsKey(hashMap, complement)) {
            int* result = (int*)malloc(sizeof(int) * 2);
            result[0] = get(hashMap, complement);
            result[1] = i;
            *returnSize = 2;
            
            freeHashMap(hashMap);
            return result;
        }
        
        put(hashMap, nums[i], i);
    }
    
    freeHashMap(hashMap);
    return NULL;
}

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize;
    
    int* result = twoSum(nums, sizeof(nums) / sizeof(nums[0]), target, &returnSize);
    
    if (result != NULL) {
        printf("Indices: %d, %d\n", result[0], result[1]);
        free(result);
    } else {
        printf("No solution found.\n");
    }
    
    return 0;
}

这段代码的思路是使用哈希表来存储每个元素的值和索引，然后遍历数组中的每个元素，查找是否存在与当前元素值相加等于目标值的另一个元素。如果存在，则返回这两个元素的索引。否则，返回NULL表示没有找到解决方案。

希望这可以帮助到你！如有任何其他问题，请随时提问。