我在 C 中使用 HashMap 来解决 TwoSum 问题做错了什么？ （-1 输入）

Question

我目前正在学习 C，以了解有关数据结构和算法 (DSA) 及其基础知识的更多信息。

从LeetCode开始，第一个问题是“二和”

我正在尝试使用 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) 作为 true/false 概念一部分的搜索函数，但我不知道如何处理这个问题。

我尝试使用AI进行审阅，但没有用。我在网上搜索了一下，但我的 hashMap 函数似乎与其他函数有点不同。

Answer 1

您正在检查键是否不是

-1

来确定特定索引处是否确实存在条目，但这是不正确的，因为

-1

是数组中的一个可能值。约束规定每个数组元素的大小最多为 10⁹，因此您可以使用

INT_MIN

作为哨兵。