使用HashMap解决C语言TwoSum问题时出错（含-1输入）

我正在学习C语言以掌握数据结构与算法（DSA）基础，从LeetCode第一题TwoSum入手，尝试用HashMap实现，但针对输入[-10, -1, -18, -19]、目标值-19的情况代码无法正常运行。

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

int hash (int key, int size){
    return abs(key) % size;
}

void insert (HashNode *hashTable, int size, int key, int value){
    int index = hash(key, size);
    while (hashTable[index].key != -1){
        index = (index + 1) % size;
    }
    hashTable[index].key = key;
    hashTable[index].value = value;
}


int search (HashNode *hashTable, int size, int key){
    int index = hash(key, size);

    while (hashTable[index].key != -1){
        if (hashTable[index].key == key){
            return hashTable[index].value;
        }
        index = (index + 1) % size;
    }
    return -1;
}
int *twoSum (int *nums, int numsSize, int target, int *returnSize) {
    int hashSize = numsSize * 2;
    HashNode *hashTable = malloc(hashSize * sizeof(HashNode));

    int *result = (int*)malloc (2 * sizeof(int));
    *returnSize = 2;


    for (int i = 0; i < hashSize; i++){
        hashTable[i].key = -1;
    }

    for (int i = 0; i < numsSize; i++){
        int complement = target - nums[i];
        int foundIndex = search(hashTable, hashSize, complement);

        if (foundIndex  != -1){
            result[0] = foundIndex;
            result[1] = i;
            free(hashTable);

            return result;
        }
        insert(hashTable, hashSize, nums[i], i);
    }

    free(hashTable);

    return result;
}

已排查HashMap逻辑，重点检查了用-1作为判断依据的search函数，但仍无法定位问题。尝试过AI代码审查和网络搜索，均未解决，请问我哪里出错了？

问题根源分析 #

你的哈希表实现有两个核心问题，都和负数处理及空节点标记有关：

1. 空节点标记与合法key冲突
   你用-1作为空节点的key标记，但测试用例中存在-1这个合法元素。当插入-1后，该节点的key被设为-1，后续search时会把这个节点误认为是空节点，直接终止循环，无法正确查找。
2. 哈希函数的负数处理缺陷
   你用abs(key) % size计算哈希值，虽然当前测试用例没触发，但如果key是INT_MIN，abs(INT_MIN)会溢出（因为INT_MIN的绝对值比INT_MAX大1）；另外这种方式没有从根本上解决负数取模的合理性，改用(key % size + size) % size能确保哈希值始终为非负索引。

修复后的代码 #

#include <limits.h>

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

// 修正哈希函数，处理负数且避免溢出
int hash(int key, int size) {
    int mod = key % size;
    return (mod + size) % size;
}

void insert(HashNode *hashTable, int size, int key, int value) {
    int index = hash(key, size);
    // 用INT_MAX作为空节点标记，避免与合法值冲突
    while (hashTable[index].key != INT_MAX) {
        index = (index + 1) % size;
    }
    hashTable[index].key = key;
    hashTable[index].value = value;
}

int search(HashNode *hashTable, int size, int key) {
    int index = hash(key, size);
    // 用INT_MAX判断空节点
    while (hashTable[index].key != INT_MAX) {
        if (hashTable[index].key == key) {
            return hashTable[index].value;
        }
        index = (index + 1) % size;
    }
    return -1;
}

int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
    int hashSize = numsSize * 2;
    HashNode *hashTable = malloc(hashSize * sizeof(HashNode));

    int *result = malloc(2 * sizeof(int));
    *returnSize = 2;

    // 初始化哈希表，用INT_MAX标记空节点
    for (int i = 0; i < hashSize; i++) {
        hashTable[i].key = INT_MAX;
        hashTable[i].value = -1;
    }

    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int foundIndex = search(hashTable, hashSize, complement);

        if (foundIndex != -1) {
            result[0] = foundIndex;
            result[1] = i;
            free(hashTable);
            return result;
        }
        insert(hashTable, hashSize, nums[i], i);
    }

    // 未找到解时，按LeetCode规范返回NULL并释放内存
    free(hashTable);
    free(result);
    *returnSize = 0;
    return NULL;
}

额外优化说明 #

• 原代码未找到解时会返回一个malloc的空数组，不符合LeetCode要求，修复后改为返回NULL并释放内存，避免内存泄漏。
• 用INT_MAX作为空节点标记，不会和任何合法的int类型值冲突（除非题目明确允许输入INT_MAX，此时可改用INT_MIN或其他特殊值）。

内容的提问来源于stack exchange，提问作者Gabriel Danilo