Two Sum问题输入[0,4,3,0]、目标0触发Address Sanitizer错误

问题场景 #

基于线性探测哈希表实现Two Sum解决方案后，在测试用例[0,4,3,0]、目标值为0时，触发Address Sanitizer错误，错误定位在hash_find函数的if(hash[k].key == num) return hash[k].val;行。

错误原因分析 #

核心问题是哈希索引计算未处理负数情况，导致数组越界访问：

• 当计算目标补数k = target - nums[i]时，可能得到负数（比如测试用例中i=2时，nums[i]=3，target=0，k=-3）。
• 在hash_find和hash_add函数中，原哈希索引计算使用(num + i) % size，而C语言中负数取模的结果符号与被除数一致（例如-3 % 4的结果为-3），直接用该负数作为数组索引会访问数组范围外的内存，触发地址错误。

修复方案 #

调整哈希索引的计算逻辑，确保最终索引始终是非负的，且处于0到size-1的合法范围内：

1. 先对原始数值取模，将结果转换为非负数；
2. 加上线性探测的偏移量i后再次取模，确保不超出数组长度。

修改后的代码 #

struct hashmap {
    int key;
    int val;
};

int hash_find(int num, int size, struct hashmap* hash) {
    int k, i;
    int base_hash = num % size;
    // 处理负数取模，确保base_hash非负
    if (base_hash < 0) {
        base_hash += size;
    }
    for(i = 0; i < size; i++) {
        k = (base_hash + i) % size;
        if(hash[k].key == num) return hash[k].val;
    }
    return -1;
}

void hash_add(int num, int size, int index, struct hashmap* hash) {
    int k, i;
    int base_hash = num % size;
    if (base_hash < 0) {
        base_hash += size;
    }
    for(i = 0; i < size; i++) {
        k = (base_hash + i) % size;
        if(hash[k].key == -9999 && hash[k].val == -9999) {
            hash[k].key = num;
            hash[k].val = index;
            return;
        }
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {       
    int* res = calloc((*returnSize = 2), sizeof(int));
    struct hashmap* hash = calloc(numsSize, sizeof(struct hashmap));
    int i;

    for(i = 0; i < numsSize; i++) {
        hash[i].key = -9999;
        hash[i].val = -9999;
    }

    for(i = 0; i < numsSize; ++i) {
        int k = target - nums[i];
        int result = hash_find(k, numsSize, hash);

        if(result >= 0) {
            res[0] = result;
            res[1] = i;
            break;
        } else {
            hash_add(nums[i], numsSize, i, hash);
        }
    }

    free(hash); // Free allocated memory for hash

    return res;
}

额外优化提示 #

当前用-9999作为哈希表的空标记，如果输入数组中存在-9999这个值，会导致逻辑错误，建议改用单独的标记位（比如在struct hashmap中增加int is_empty字段）来标识该位置是否为空。

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