LeetCode Q1 两数之和单遍哈希表C语言解法运行失败排查

• 栈上哈希表未初始化：你声明的node *table[N]是变长数组，存储在栈空间，初始值为随机垃圾值而非NULL，遍历桶和插入时判断table[bucket] == NULL完全失效，大概率触发野指针访问导致段错误。需要在创建数组后遍历所有桶，手动赋值为NULL。
• 函数嵌套定义不符合C标准：你将hash函数定义在twoSum函数内部，这是GCC等编译器的非标准扩展，在标准C环境下会直接编译失败。需要把hash函数移到twoSum外部，或者直接把哈希计算逻辑内联到代码里。
• 未设置returnSize输出参数：题目要求通过returnSize指针返回结果数组的长度，你没有对*returnSize赋值，调用方无法感知返回数组的有效长度，绝大多数判题平台会直接判错。找到解返回前需要设置*returnSize = 2，无符合解时设置*returnSize = 0。
• 未处理无符合解的分支：如果遍历完整个数组都没有找到符合要求的两个数，函数走到末尾没有返回值，属于未定义行为。这种场景下需要释放已经申请的out数组，返回NULL，或者按题目要求返回空结果。
• 哈希函数未兼容负数输入：如果num为负数，num * 31337 % N的结果在C标准中符号与被除数一致，也就是为负数，赋值给无符号的返回值后会得到远大于N的数值，导致访问table数组越界。需要先将输入值转为无符号整数再做哈希计算，或者对负数结果做偏移处理保证桶索引在[0, N-1]范围内。
• 存在内存泄漏隐患：你为每个哈希节点申请了堆内存，但函数返回时没有释放这些节点的内存，虽然题目说明调用方会free返回的结果数组，但哈希节点的内存会发生泄漏。如果是生产环境使用需要补充哈希表销毁逻辑，算法题场景下通常可以忽略。

修正后代码 #

#include <stdlib.h>

typedef struct node{
    int num;
    int index;
    struct node *next;
} node;

unsigned int hash(int num, unsigned int bucket_num){
    // 处理负数，转成无符号后再计算哈希
    unsigned int n = (unsigned int)num;
    return n * 31337 % bucket_num;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    const unsigned int N = (unsigned int)numsSize * 2;
    // 用calloc申请哈希表数组，自动初始化为NULL
    node **table = (node**)calloc(N, sizeof(node*));
    int *out = (int*)malloc(2 * sizeof(int));
     
    for (int i = 0; i < numsSize; i++){
        int compliment = target - nums[i];
        unsigned int compliment_bucket = hash(compliment, N);
        for (node *n = table[compliment_bucket]; n != NULL; n = n->next){
            if (compliment == n->num){
                out[0] = n->index;
                out[1] = i;
                *returnSize = 2;
                // 算法题场景下省略哈希节点释放逻辑，生产环境需补充
                free(table);
                return out;
            }
        }

        unsigned int bucket = hash(nums[i], N);
        node *tmp = (node*)calloc(1, sizeof(node));
        tmp->num = nums[i];
        tmp->index = i;
        tmp->next = table[bucket];
        table[bucket] = tmp;
    }

    // 无符合解的分支处理
    free(out);
    free(table);
    *returnSize = 0;
    return NULL;
}

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