LeetCode TwoSum哈希表实现数组越界运行时错误求助

我在LeetCode提交的TwoSum哈希表实现出现运行时错误：runtime error: index -576 out of bounds for type 'int [10000]'，错误定位在hash_search()函数的第一行代码：

if(hash_arr[(n + TABLE_SIZE/2) % TABLE_SIZE] != -1){}

我推测是测试用例运行时出现了非法负索引，但无法复现该场景。作为C语言新手，搜索同类问题后仍未解决，请求帮助排查索引问题，完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10000

static int hash_arr[TABLE_SIZE];
int hash_insert();
void hash_init();
int hash_search();


// LeetCode function
//
// ret_arr[] is the array of two elements with the indices of the
// values that add up to the target value.
int *twoSum(int *nums, int numsSize, int target, int *returnSize){

    int i, j;
    int *ret_arr = (int*)malloc(2 * sizeof(int));

    // Validation
    if(ret_arr == NULL){
        *returnSize = 0;
        return NULL;
    }

    hash_init();

    for(i = 0; i < numsSize; i++){
        if((j = hash_search(target - nums[i])) == -1){
            hash_insert(nums[i], i);
        }else{
            // if j is already in the hash table
            ret_arr[0] = i;
            ret_arr[1] = j;
            *returnSize = 2;
            return ret_arr;
        }
    }
    *returnSize = 0;
    free(ret_arr);
    return NULL;
}

// int main(void) for testing purposes
int main(void){

    int nums[4] = {2,7,11,15};
    int numsSize = sizeof(nums)/sizeof(nums[0]);
    int returnSize = 0;
    int target = 9;
    int *p = NULL;

    p = twoSum(nums, numsSize, target, &returnSize);

    if(returnSize == 0){
        printf("Not found\n");
    }else{
        printf("Found at indices %d and %d\n", p[0], p[1]);
        free(p);
    }
}

// Initialization
void hash_init(){
    for(int i = 0; i < TABLE_SIZE; i++){
        hash_arr[i] = -1;
    }
}


int hash_insert(int n, int j){
    // location available
    if(hash_arr[(n + TABLE_SIZE/2) % TABLE_SIZE] == -1){
        hash_arr[(n + TABLE_SIZE/2) % TABLE_SIZE] = j;
        return 0;
    }else{
        // if location already being used
        return -1;
    }
}

int hash_search(int n){
    if(hash_arr[(n + TABLE_SIZE/2) % TABLE_SIZE] != -1){
        return hash_arr[(n + TABLE_SIZE/2) % TABLE_SIZE];
    }else{
        return -1;
    }
}

问题根源 #

C语言中，负数取模的结果仍为负数。当n的绝对值大于TABLE_SIZE/2时，n + TABLE_SIZE/2会变成负数，此时对TABLE_SIZE取模得到的结果还是负数，直接作为数组索引就会触发越界错误。

举个例子：当n = -6000，TABLE_SIZE=10000，TABLE_SIZE/2=5000，计算-6000 + 5000 = -1000，-1000 % 10000在C中的结果是-1000，这显然是非法的数组索引。

修复方案 #

要确保哈希计算结果始终是非负数，只需在取模后加上TABLE_SIZE，再取一次模，就能保证结果落在0到TABLE_SIZE-1的合法范围内：

修改哈希索引的计算表达式为：

((n + TABLE_SIZE/2) % TABLE_SIZE + TABLE_SIZE) % TABLE_SIZE

修改后的hash_insert函数 #

int hash_insert(int n, int j){
    int idx = ((n + TABLE_SIZE/2) % TABLE_SIZE + TABLE_SIZE) % TABLE_SIZE;
    if(hash_arr[idx] == -1){
        hash_arr[idx] = j;
        return 0;
    }else{
        return -1;
    }
}

修改后的hash_search函数 #

int hash_search(int n){
    int idx = ((n + TABLE_SIZE/2) % TABLE_SIZE + TABLE_SIZE) % TABLE_SIZE;
    if(hash_arr[idx] != -1){
        return hash_arr[idx];
    }else{
        return -1;
    }
}

额外优化建议 #

当前实现还有一个隐患：没有处理哈希冲突。当不同的n计算出相同索引时，直接返回插入失败，会导致部分测试用例无法通过。可以用线性探测法解决冲突，同时，当前哈希表只存储索引，无法验证对应的值是否匹配目标值，容易出现错误匹配，建议改用结构体存储键值对：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h> // 引入INT_MIN

#define TABLE_SIZE 10000

typedef struct {
    int val;
    int idx;
} HashEntry;

static HashEntry hash_arr[TABLE_SIZE];
int hash_insert(int n, int j);
void hash_init();
int hash_search(int n);

int *twoSum(int *nums, int numsSize, int target, int *returnSize){
    int i, j;
    int *ret_arr = (int*)malloc(2 * sizeof(int));

    if(ret_arr == NULL){
        *returnSize = 0;
        return NULL;
    }

    hash_init();

    for(i = 0; i < numsSize; i++){
        if((j = hash_search(target - nums[i])) == -1){
            hash_insert(nums[i], i);
        }else{
            ret_arr[0] = j;
            ret_arr[1] = i;
            *returnSize = 2;
            return ret_arr;
        }
    }
    *returnSize = 0;
    free(ret_arr);
    return NULL;
}

void hash_init(){
    for(int i = 0; i < TABLE_SIZE; i++){
        hash_arr[i].val = INT_MIN; // 用INT_MIN标记空位置
        hash_arr[i].idx = -1;
    }
}

int hash_insert(int n, int j){
    int idx = ((n + TABLE_SIZE/2) % TABLE_SIZE + TABLE_SIZE) % TABLE_SIZE;
    // 线性探测找可用位置
    for(int i = 0; i < TABLE_SIZE; i++){
        int current_idx = (idx + i) % TABLE_SIZE;
        if(hash_arr[current_idx].val == INT_MIN){
            hash_arr[current_idx].val = n;
            hash_arr[current_idx].idx = j;
            return 0;
        }
    }
    return -1;
}

int hash_search(int n){
    int idx = ((n + TABLE_SIZE/2) % TABLE_SIZE + TABLE_SIZE) % TABLE_SIZE;
    for(int i = 0; i < TABLE_SIZE; i++){
        int current_idx = (idx + i) % TABLE_SIZE;
        if(hash_arr[current_idx].val == INT_MIN){
            return -1; // 空位置，说明不存在
        }
        if(hash_arr[current_idx].val == n){
            return hash_arr[current_idx].idx;
        }
    }
    return -1;
}

这个版本既解决了负索引问题，又处理了哈希冲突，还能准确验证目标值，通过所有LeetCode测试用例的概率更高。

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