从小到大看着LeetCode题库里两数之和长期挂在第一题的位置我一直觉得它像一道门槛——跨过去的人会觉得哈希表真香跨不过去的人则容易被C语言里那一堆结构体、指针、malloc劝退。说句实话这道题在C语言解法里是最能体现为什么需要用哈希表的入门题之一它不涉及复杂的递归、贪心或者动态规划纯粹考察一件事——当你需要在遍历中快速查找某个值是否存在时哈希表为什么是效率最优的选择。如果你正在用C语言刷LeetCode或者刚刚开始接触哈希表数据结构这篇文章会从暴力解法开始逐步拆解哈希表的原理最终给出一份可以直接提交的完整C代码。我会把哈希桶的设计、哈希函数的选择、内存分配这些实操细节全部摊开讲并且分享一些我在LeetCode上反复提交时踩过的坑。不管是刚入门的小白还是想看C语言工程化写法的老手应该都能从中拿到点东西。1. 一道简单题的前置认知暴力解法为什么被嫌弃1.1 题目到底在问什么先把题目复述一遍给你一个整数数组nums和一个整数目标值target你需要在数组中找出和为目标值target的两个整数并返回它们的数组下标。假设每种输入只会对应一个答案且同一个元素不能使用两次。LeetCode给C语言的函数签名长这样int* twoSum(int* nums, int numsSize, int target, int* returnSize);nums传入的整型数组numsSize数组长度target目标和returnSize你要告诉调用者返回数组的长度这里固定填 2可能第一次接触这个签名的人会懵为什么还要一个returnSize指针因为C语言无法直接返回数组的长度信息返回的只是一个int*调用者得靠额外的参数才知道你返回了几个元素。这个设计在LeetCode的所有C语言题解里几乎都会出现建议一开始就养成习惯不管函数内部做了什么最后一定要给*returnSize赋值否则判题系统无法正确读取结果。1.2 暴力解法的效率账拿到这道题正常人第一反应都是两层循环int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* result (int*)malloc(2 * sizeof(int)); for (int i 0; i numsSize; i) { for (int j i 1; j numsSize; j) { if (nums[i] nums[j] target) { result[0] i; result[1] j; *returnSize 2; return result; } } } *returnSize 0; return NULL; }逻辑完全正确功能也没问题。但问题出在效率外层循环跑n次内层循环在极端情况下要跑接近n次总复杂度是 O(n²)。当n是几千的时候程序还能勉强跑完但当n到达几十万甚至上百万时O(n²) 的执行时间会迅速膨胀到无法接受的程度。我打个比方。你在一个能容纳一万人的体育馆里找两个人要求他们的年龄加起来等于某个数。暴力做法是站到第一个人面前然后挨个问剩下的九千九百九十九个人的年龄没找到再去问第二个人再把剩下的九千九百九十八个人问一遍……一万个人你要开口问大约五千万次。这当然能完成但没人觉得这是聪明的做法。LeetCode之所以把题目难度标成 Easy不是因为暴力法能过而是因为存在 O(n) 的思路。所以才说这道题真正的考点是你知不知道有比暴力查找更快的索引方式。2. 为什么哈希表能带来质变从O(n²)到O(n)的思维转变2.1 暴力解法浪费在哪里仔细看暴力解法内层循环做了一件很笨的事每次都在剩余的数组元素里线性查找target - nums[i]。这个查找过程每次都是 O(n)而查找又是整个算法的核心操作所以整体复杂度上不去。如果我们能把查找一个元素是否存在于集合中并且快速拿到它的下标这一步从 O(n) 优化到 O(1)那么整个遍历只要一遍就能完成走到nums[i]时只要 O(1) 看一眼之前有没有存过target - nums[i]即可。于是总复杂度就是 O(n)。问题来了怎么做到 O(1) 查找答案就是哈希表。哈希表本质上是一个空间换时间的结构——我们额外用一块内存来记录已经遍历过的元素从而把查找的时间降下来。2.2 哈希表的核心机制哈希表也叫散列表它的核心思想是通过一个哈希函数把关键字key直接映射为数组下标然后把值value存储在这个下标对应的位置上。这样查找时只要重新计算哈希函数就能直接定位到数据所在的位置不需要逐个比较。打个比方。小区门口有快递柜柜门上贴着编号。快递员一开始就把每个柜子的编号通过一种固定规则关联到收件人的手机尾号。等你去取件时只要报出手机尾号快递员一算就知道你的件在哪个柜子不用把一百个柜子全打开找一遍。哈希函数就是这个从手机尾号到柜号的映射规则。当然生活不会永远这么完美。两个不同关键字可能映射到同一个下标这就是哈希冲突。解决冲突有很多种办法C语言手写时最常用的有两种开放寻址法冲突了就往后找空位链地址法每个桶里不是存一个元素而是存一个链表的头结点冲突的元素依次挂到链表后面对于LeetCode这种判题环境我用得最多的是链地址法。原因很简单实现直观、删除简单、代码容易检查。后面的完整代码就是基于链地址法实现的。还有一个概念叫装填因子哈希表中已有的元素个数除以桶的数量。装填因子越小冲突越少查找效率越高但内存浪费也越多装填因子越大空间利用越充分但冲突会变多链表变长性能退化。工程上一般控制在 0.75 左右这是经验值。刷题时为了简单桶数直接取数组长度的两倍装填因子就是 0.5冲突概率很小做起来很舒服。2.3 在这道题里哈希表到底存什么哈希表里存的key和value分别是key 数组元素值value 该元素的下标。算法流程是这样的创建一个空的哈希表从头到尾遍历数组假设当前元素是nums[i]在哈希表里查找target - nums[i]如果找到了说明之前已经遍历到某个下标j满足nums[j] target - nums[i]直接把[j, i]返回即可如果没找到就把(nums[i], i)插入哈希表然后继续往后走遍历结束还没找到按题意不会发生但严谨起见还是返回空并设置returnSize 0为什么一定要一边遍历一边插入而不是先把所有元素插进去再查找原因在于如果先把所有元素插入哈希表再回头找target - nums[i]那么需要额外判断查到的下标不能等于 i 自身防止同一个元素用了两次。而边遍历边插入的方案天然避免了这个问题——哈希表里存的都是之前遍历过的元素下标不可能与当前下标相同。这是实现上很巧妙的一个细节。3. C语言版哈希表怎么落地手写链地址哈希表3.1 C语言为什么没有现成的哈希表用过C的人都知道unordered_map用过Java的人都知道HashMapPython里甚至有现成的dict它们在底层就是哈希表。但C语言的标准库里没有这些高级容器LeetCode的判题环境也不允许你随手引入第三方库。所以在C语言题解中哈希表必须自己从头实现。这算不算麻烦确实比写map[key] value要麻烦得多。但换个角度想正因为C语言没有现成的你才有机会把一个哈希表的每个细节都看得清清楚楚哈希函数怎么选、冲突怎么解决、内存怎么分配和释放。这些底层细节搞明白了以后用任何高级语言的哈希表都只是API熟练度的问题。以我在LeetCode上刷题的经验C语言的劣势是代码量大优势是一旦把结构体、指针、内存这些都理顺对数据结构的理解深度会远高于直接调API的人。3.2 哈希桶结构体的设计链地址法需要两个东西一个Node结构体表示链表节点一个Node**数组表示桶数组。typedef struct Node { int key; int val; struct Node* next; } Node;key存数组元素值val存数组下标也就是最终要返回的值next指向下一个冲突节点的指针桶数组用Node** buckets表示每个元素是一个链表头指针。初始化时需要让所有桶都指向 NULL这一点特别重要。C语言的局部数组不会自动清零malloc出来的内存内容也是不确定的必须显式初始化否则后面遍历链表时会拿着野指针乱撞。哈希函数的选择上最常用的做法是取模int hash(int key, int size) { if (key 0) { return (key % size size) % size; } return key % size; }有人会问为什么要对负数做两次取模因为C语言里负数取模的结果可能是负数。比如-7 % 5在C语言里结果是-2。如果直接用这个负数当数组下标程序会崩溃。(key % size size) % size的做法能保证结果一定落在[0, size - 1]之间。相比直接用abs(key) % size这个写法更稳妥因为abs(INT_MIN)在某些编译器上会返回负数而上面的取模写法不会踩到这个坑。3.3 插入与查找的完整实现插入用头插法就是把新节点挂到链表的最前面。头插法的好处是时间复杂度 O(1)而且代码特别简洁void insert(Node** buckets, int size, int key, int val) { int index hash(key, size); Node* newNode (Node*)malloc(sizeof(Node)); newNode-key key; newNode-val val; newNode-next buckets[index]; buckets[index] newNode; }先让新节点的next指向原来的链表头再把桶的头指针更新为新节点两步就完成了头插。查找函数就是走到哈希函数算出来的桶下标位置然后沿着链表逐个比较keyint find(Node** buckets, int size, int key, int* foundVal) { int index hash(key, size); Node* cur buckets[index]; while (cur ! NULL) { if (cur-key key) { *foundVal cur-val; return 1; } cur cur-next; } return 0; }找到返回 1并通过指针参数把value传出去没找到返回 0。这个设计避免了用特殊值比如 -1表示没找到时产生的歧义——万一某个元素的下标真的就是 -1 呢在C语言里能用指针回传结果就尽量用指针不要用哨兵值。3.4 释放内存被很多人忽略的最后一步写完题目很多人直接提交就算完事完全不释放哈希表的内存。在LeetCode上确实不影响判题结果但会造成内存泄漏。特别是当判题系统在一个进程里连续跑几百个测试用例时泄漏会累积起来最终可能导致内存不足。我一般会在返回结果之前把哈希表整张释放掉void freeTable(Node** buckets, int size) { for (int i 0; i size; i) { Node* cur buckets[i]; while (cur ! NULL) { Node* tmp cur; cur cur-next; free(tmp); } } free(buckets); }每个链表节点都要单独释放最后释放桶数组本身。这个过程虽然麻烦但能帮你养成一个好习惯每次malloc都和free配对出现。实际工程中内存泄漏是非常隐蔽的bug从刷题开始就养成规范意识后面写项目时能少掉很多头发。4. 完整可提交的C代码一次遍历版twoSum4.1 代码全文把上面的组件拼起来再加上twoSum主体逻辑就是一份可以直接提交到LeetCode的完整代码#include stdlib.h #include string.h typedef struct Node { int key; int val; struct Node* next; } Node; int hash(int key, int size) { if (key 0) { return (key % size size) % size; } return key % size; } void insert(Node** buckets, int size, int key, int val) { int index hash(key, size); Node* newNode (Node*)malloc(sizeof(Node)); newNode-key key; newNode-val val; newNode-next buckets[index]; buckets[index] newNode; } int find(Node** buckets, int size, int key, int* foundVal) { int index hash(key, size); Node* cur buckets[index]; while (cur ! NULL) { if (cur-key key) { *foundVal cur-val; return 1; } cur cur-next; } return 0; } void freeTable(Node** buckets, int size) { for (int i 0; i size; i) { Node* cur buckets[i]; while (cur ! NULL) { Node* tmp cur; cur cur-next; free(tmp); } } free(buckets); } int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int tableSize numsSize * 2; Node** buckets (Node**)calloc(tableSize, sizeof(Node*)); for (int i 0; i numsSize; i) { int complement target - nums[i]; int foundVal; if (find(buckets, tableSize, complement, foundVal)) { int* result (int*)malloc(2 * sizeof(int)); result[0] foundVal; result[1] i; *returnSize 2; freeTable(buckets, tableSize); return result; } insert(buckets, tableSize, nums[i], i); } freeTable(buckets, tableSize); *returnSize 0; return NULL; }4.2 逐步拆解主体逻辑这段twoSum的核心流程就是前面讲的边遍历边查找边插入tableSize numsSize * 2桶数组长度取数组长度的两倍保证装填因子不超过 0.5冲突很少calloc(tableSize, sizeof(Node*))calloc会把内存清零也就是把所有桶初始化为 NULL这一步很省心遍历到nums[i]时先算complement target - nums[i]然后到哈希表里查找找到就分配结果数组并填好下标然后释放哈希表返回结果没找到就执行insert把当前元素存入哈希表继续循环如果循环走完还没找到按题目的约束不会发生释放资源后返回 NULL并设置*returnSize 0每一步的顺序都是精心安排过的先查再插保证了不可能出现同一个元素和自己匹配的情况。4.3 边界条件与隐藏细节C语言的题解里最容易翻车的不是算法思路而是内存和指针的边角细节。以下几个点是我反复踩过、后来形成肌肉记忆的地方结果数组必须用 malloc 分配。C语言函数里如果返回一个局部数组的首地址函数结束后栈帧被回收这个指针就成了悬垂指针。LeetCode的判题系统读到的是垃圾数据程序行为不可预测。*returnSize一定要赋值。如果你忘了设置它判题系统就不知道返回数组有多长可能会越界读取内存。哪怕返回 NULL也要把*returnSize设为 0。负数的哈希处理。上面用的是两次取模方式比较稳妥。有些题解用abs(key) % size一般情况下没问题但要意识到abs的边界风险。calloc和malloc memset是等价的。我选择calloc纯粹是可以少写一行初始化代码。如果要用malloc必须立刻补一句memset(buckets, 0, sizeof(Node*) * tableSize)。5. 我在LeetCode上反复提交时踩过的坑5.1 哈希桶初始化遗漏野指针崩溃现场有一段时间我写C语言代码图省事初始化哈希表时用了malloc却忘记清零直接在后面插入节点。结果程序运行到链表遍历时访问了一个完全随机的地址直接段错误。排查了很久才意识到malloc返回的内存是不确定的内容它不会自动替你清零。所以桶数组初始状态可能是一些乱七八糟的垃圾指针。你往链表头部插入节点时newNode-next buckets[index]就把这个垃圾地址挂到了链表上。等到查找时遍历链表程序就会按垃圾地址去访问内存崩溃是必然的。后来我强制自己遵守一个规则只要分配了哈希桶数组下一步必做清零操作。用calloc也好用memset也好总之这一步不能省。5.2 内存释放顺序搞反先释放桶数组再释放链表节点还有一个我犯过不止一次的错释放哈希表时先free(buckets)再想着去释放链表节点。这完全把顺序搞反了——桶数组都没了链表头指针从哪来程序在第二次释放时就会访问已释放的内存。正确的顺序一定是先遍历所有桶把每个桶下面的链表节点逐个释放干净最后再释放桶数组本身。也就是我前面freeTable里的顺序。实在记不住的话可以想象成拆房子得先搬走屋里的家具才能拆承重墙最后拆除大楼的立柱。5.3 哈希函数负数取模踩坑下标变成负数LeetCode的两数之和题目里nums中的元素是允许出现负数的。我第一次提交的哈希函数是这样写的int hash(int key, int size) { return key % size; }当时数组里碰巧全是正数测试样例都过了。后来我换了一套包含负数的测试数据程序直接数组越界判题系统报了 Runtime Error。原因前面提到过C语言的求余运算在处理负数时结果可能是负数。-3 % 5在C语言里等于-3如果你拿这个当数组下标当然越界。从那之后我的哈希函数就固定成了(key % size size) % size这种写法不为别的就为稳妥。5.4 返回值里下标顺序不一致导致提交失败还有一次提交失败不是因为算法错而是因为返回的[j, i]顺序和请求的下标顺序不一致。详情记不太清了只记得最后是通过仔细读题才发现的。这里给大家的提醒是LeetCode对返回的两个下标要求是可以乱序的你的代码里先找到哪个下标就把哪个放前面这个完全由自己控制但要保证最终返回的两个值确实来自两个不同的数组位置。我在代码里习惯先返回之前存进哈希表的下标foundVal再返回当前遍历到的下标i。这个顺序写清楚后就没有再出过类似问题。5.5 LeetCode判题环境中的内存泄漏问题可能很多人觉得LeetCode跑完一个测试用例就会回收内存不释放也没关系。但我在刷题时遇到过个别题目如果每次调用都泄漏一点内存多次调用之后程序会变得异常慢甚至崩溃。LeetCode的判题常常会用一个进程连续调用你的函数多次。twoSum这种函数每调用一次哈希表就泄漏一次。虽然单次量很小但如果测试用例有几万个那泄漏的内存就会非常可观。因此哪怕LeetCode不报错我也会在返回之前释放掉所有动态分配的内存。这是代码洁癖更是工程素养。6. 这道题之外哈希表的变体和后续刷题方向6.1 从Two Sum到Three Sum哈希表还管用吗很多人在做完两数之和后会自然地想三数之和是不是也能用哈希表结论是可以但一般不建议这么做。Three Sum 的经典解法是排序 双指针时间复杂度 O(n²)如果硬要用哈希表去重问题会非常麻烦。但哈希表思想在两数之和的变体题目中依然非常实用比如LeetCode 167. Two Sum II - Input Array Is Sorted数组有序可以用双指针也可以用哈希表LeetCode 1. 这道题的多个版本HashMap存储值到下标的映射的通用模板可以套到很多题目里我的建议是两数之和用哈希表三数之和用排序双指针四数之和则需要双指针加一层循环或者用哈希表辅助。不同的题目有不同最适合的解法这个需要自己在刷题中慢慢积累感觉。6.2 哈希表在LeetCode高频题中的位置哈希表绝不只是为这道题准备的。我简单梳理了一下LeetCode上高频考察哈希表的题型供你做一个后续刷题计划题目难度哈希表的作用1. Two SumEasy值到下标的映射O(1)查找补数387. First Unique Character in a StringEasy统计字符出现次数242. Valid AnagramEasy统计字符频率做对比49. Group AnagramsMedium排序后的字符串作为哈希表key3. Longest Substring Without Repeating CharactersMedium记录字符最后一次出现的位置560. Subarray Sum Equals KMedium前缀和 哈希表非常经典128. Longest Consecutive SequenceMedium用哈希集合判断连续序列的起点其中 560 题是我个人认为最能体现哈希表空间换时间威力的题目强烈推荐在掌握本题之后去挑战一下。6.3 学习建议C语言刷题到底值不值得这个问题我经常被问到。说实话如果你现在时间紧迫、面试在即用C或Python刷题效率绝对更高因为内置的哈希表可以随手调用。但如果你是想扎实地打数据结构基本功那我非常推荐用C语言过一遍简单题和中等题。原因很简单高级语言把哈希表的复杂度封装在标准库里你调用时只能感受到快感受不到为什么快。而手写一遍哈希表后你会彻底理解key通过哈希函数映射到桶下标冲突时链地址法如何工作为什么查找平均 O(1)这些概念。以后再回头看 C 的unordered_map或者 Python 的dict你会觉得它们就是封装好的同一套东西。我的个人经验是用C语言刷题的前一百道会非常痛苦因为每个基础数据结构都要自己造轮子光是链表、哈希表、栈、队列这四件套就能写几百行代码。但一旦熬过去这个阶段后续面对任何算法题时你对底层发生了什么是有画面感的。这种底层认知是刷多少道调用API的题都换不来的。结尾从两数之和这道题延伸出去我最大的体会是算法题最值钱的不是答案而是你在写答案过程中建立起来的底层直觉。我第一次看到哈希表时也是一头雾水——为什么要额外开一块内存为什么取模能定位到桶直到自己动手把链地址法一个节点一个节点地串起来这些疑问才真正消失。如果你也是C语言初学者被这道题的代码量吓到了别灰心。这些结构体、哈希函数、内存释放的模板每多写一次就熟练一分。先把这道题的完整代码在自己机器上跑通再亲手把哈希表清空函数加上动手敲一遍比看十遍题解都有用。等你把这道题彻底吃透再回头看LeetCode top 100里那些考哈希表的中等题会觉得心里有底很多。 C语言手写哈希表：详解LeetCode两数之和高效解法
从小到大看着LeetCode题库里两数之和长期挂在第一题的位置我一直觉得它像一道门槛——跨过去的人会觉得哈希表真香跨不过去的人则容易被C语言里那一堆结构体、指针、malloc劝退。说句实话这道题在C语言解法里是最能体现为什么需要用哈希表的入门题之一它不涉及复杂的递归、贪心或者动态规划纯粹考察一件事——当你需要在遍历中快速查找某个值是否存在时哈希表为什么是效率最优的选择。如果你正在用C语言刷LeetCode或者刚刚开始接触哈希表数据结构这篇文章会从暴力解法开始逐步拆解哈希表的原理最终给出一份可以直接提交的完整C代码。我会把哈希桶的设计、哈希函数的选择、内存分配这些实操细节全部摊开讲并且分享一些我在LeetCode上反复提交时踩过的坑。不管是刚入门的小白还是想看C语言工程化写法的老手应该都能从中拿到点东西。1. 一道简单题的前置认知暴力解法为什么被嫌弃1.1 题目到底在问什么先把题目复述一遍给你一个整数数组nums和一个整数目标值target你需要在数组中找出和为目标值target的两个整数并返回它们的数组下标。假设每种输入只会对应一个答案且同一个元素不能使用两次。LeetCode给C语言的函数签名长这样int* twoSum(int* nums, int numsSize, int target, int* returnSize);nums传入的整型数组numsSize数组长度target目标和returnSize你要告诉调用者返回数组的长度这里固定填 2可能第一次接触这个签名的人会懵为什么还要一个returnSize指针因为C语言无法直接返回数组的长度信息返回的只是一个int*调用者得靠额外的参数才知道你返回了几个元素。这个设计在LeetCode的所有C语言题解里几乎都会出现建议一开始就养成习惯不管函数内部做了什么最后一定要给*returnSize赋值否则判题系统无法正确读取结果。1.2 暴力解法的效率账拿到这道题正常人第一反应都是两层循环int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* result (int*)malloc(2 * sizeof(int)); for (int i 0; i numsSize; i) { for (int j i 1; j numsSize; j) { if (nums[i] nums[j] target) { result[0] i; result[1] j; *returnSize 2; return result; } } } *returnSize 0; return NULL; }逻辑完全正确功能也没问题。但问题出在效率外层循环跑n次内层循环在极端情况下要跑接近n次总复杂度是 O(n²)。当n是几千的时候程序还能勉强跑完但当n到达几十万甚至上百万时O(n²) 的执行时间会迅速膨胀到无法接受的程度。我打个比方。你在一个能容纳一万人的体育馆里找两个人要求他们的年龄加起来等于某个数。暴力做法是站到第一个人面前然后挨个问剩下的九千九百九十九个人的年龄没找到再去问第二个人再把剩下的九千九百九十八个人问一遍……一万个人你要开口问大约五千万次。这当然能完成但没人觉得这是聪明的做法。LeetCode之所以把题目难度标成 Easy不是因为暴力法能过而是因为存在 O(n) 的思路。所以才说这道题真正的考点是你知不知道有比暴力查找更快的索引方式。2. 为什么哈希表能带来质变从O(n²)到O(n)的思维转变2.1 暴力解法浪费在哪里仔细看暴力解法内层循环做了一件很笨的事每次都在剩余的数组元素里线性查找target - nums[i]。这个查找过程每次都是 O(n)而查找又是整个算法的核心操作所以整体复杂度上不去。如果我们能把查找一个元素是否存在于集合中并且快速拿到它的下标这一步从 O(n) 优化到 O(1)那么整个遍历只要一遍就能完成走到nums[i]时只要 O(1) 看一眼之前有没有存过target - nums[i]即可。于是总复杂度就是 O(n)。问题来了怎么做到 O(1) 查找答案就是哈希表。哈希表本质上是一个空间换时间的结构——我们额外用一块内存来记录已经遍历过的元素从而把查找的时间降下来。2.2 哈希表的核心机制哈希表也叫散列表它的核心思想是通过一个哈希函数把关键字key直接映射为数组下标然后把值value存储在这个下标对应的位置上。这样查找时只要重新计算哈希函数就能直接定位到数据所在的位置不需要逐个比较。打个比方。小区门口有快递柜柜门上贴着编号。快递员一开始就把每个柜子的编号通过一种固定规则关联到收件人的手机尾号。等你去取件时只要报出手机尾号快递员一算就知道你的件在哪个柜子不用把一百个柜子全打开找一遍。哈希函数就是这个从手机尾号到柜号的映射规则。当然生活不会永远这么完美。两个不同关键字可能映射到同一个下标这就是哈希冲突。解决冲突有很多种办法C语言手写时最常用的有两种开放寻址法冲突了就往后找空位链地址法每个桶里不是存一个元素而是存一个链表的头结点冲突的元素依次挂到链表后面对于LeetCode这种判题环境我用得最多的是链地址法。原因很简单实现直观、删除简单、代码容易检查。后面的完整代码就是基于链地址法实现的。还有一个概念叫装填因子哈希表中已有的元素个数除以桶的数量。装填因子越小冲突越少查找效率越高但内存浪费也越多装填因子越大空间利用越充分但冲突会变多链表变长性能退化。工程上一般控制在 0.75 左右这是经验值。刷题时为了简单桶数直接取数组长度的两倍装填因子就是 0.5冲突概率很小做起来很舒服。2.3 在这道题里哈希表到底存什么哈希表里存的key和value分别是key 数组元素值value 该元素的下标。算法流程是这样的创建一个空的哈希表从头到尾遍历数组假设当前元素是nums[i]在哈希表里查找target - nums[i]如果找到了说明之前已经遍历到某个下标j满足nums[j] target - nums[i]直接把[j, i]返回即可如果没找到就把(nums[i], i)插入哈希表然后继续往后走遍历结束还没找到按题意不会发生但严谨起见还是返回空并设置returnSize 0为什么一定要一边遍历一边插入而不是先把所有元素插进去再查找原因在于如果先把所有元素插入哈希表再回头找target - nums[i]那么需要额外判断查到的下标不能等于 i 自身防止同一个元素用了两次。而边遍历边插入的方案天然避免了这个问题——哈希表里存的都是之前遍历过的元素下标不可能与当前下标相同。这是实现上很巧妙的一个细节。3. C语言版哈希表怎么落地手写链地址哈希表3.1 C语言为什么没有现成的哈希表用过C的人都知道unordered_map用过Java的人都知道HashMapPython里甚至有现成的dict它们在底层就是哈希表。但C语言的标准库里没有这些高级容器LeetCode的判题环境也不允许你随手引入第三方库。所以在C语言题解中哈希表必须自己从头实现。这算不算麻烦确实比写map[key] value要麻烦得多。但换个角度想正因为C语言没有现成的你才有机会把一个哈希表的每个细节都看得清清楚楚哈希函数怎么选、冲突怎么解决、内存怎么分配和释放。这些底层细节搞明白了以后用任何高级语言的哈希表都只是API熟练度的问题。以我在LeetCode上刷题的经验C语言的劣势是代码量大优势是一旦把结构体、指针、内存这些都理顺对数据结构的理解深度会远高于直接调API的人。3.2 哈希桶结构体的设计链地址法需要两个东西一个Node结构体表示链表节点一个Node**数组表示桶数组。typedef struct Node { int key; int val; struct Node* next; } Node;key存数组元素值val存数组下标也就是最终要返回的值next指向下一个冲突节点的指针桶数组用Node** buckets表示每个元素是一个链表头指针。初始化时需要让所有桶都指向 NULL这一点特别重要。C语言的局部数组不会自动清零malloc出来的内存内容也是不确定的必须显式初始化否则后面遍历链表时会拿着野指针乱撞。哈希函数的选择上最常用的做法是取模int hash(int key, int size) { if (key 0) { return (key % size size) % size; } return key % size; }有人会问为什么要对负数做两次取模因为C语言里负数取模的结果可能是负数。比如-7 % 5在C语言里结果是-2。如果直接用这个负数当数组下标程序会崩溃。(key % size size) % size的做法能保证结果一定落在[0, size - 1]之间。相比直接用abs(key) % size这个写法更稳妥因为abs(INT_MIN)在某些编译器上会返回负数而上面的取模写法不会踩到这个坑。3.3 插入与查找的完整实现插入用头插法就是把新节点挂到链表的最前面。头插法的好处是时间复杂度 O(1)而且代码特别简洁void insert(Node** buckets, int size, int key, int val) { int index hash(key, size); Node* newNode (Node*)malloc(sizeof(Node)); newNode-key key; newNode-val val; newNode-next buckets[index]; buckets[index] newNode; }先让新节点的next指向原来的链表头再把桶的头指针更新为新节点两步就完成了头插。查找函数就是走到哈希函数算出来的桶下标位置然后沿着链表逐个比较keyint find(Node** buckets, int size, int key, int* foundVal) { int index hash(key, size); Node* cur buckets[index]; while (cur ! NULL) { if (cur-key key) { *foundVal cur-val; return 1; } cur cur-next; } return 0; }找到返回 1并通过指针参数把value传出去没找到返回 0。这个设计避免了用特殊值比如 -1表示没找到时产生的歧义——万一某个元素的下标真的就是 -1 呢在C语言里能用指针回传结果就尽量用指针不要用哨兵值。3.4 释放内存被很多人忽略的最后一步写完题目很多人直接提交就算完事完全不释放哈希表的内存。在LeetCode上确实不影响判题结果但会造成内存泄漏。特别是当判题系统在一个进程里连续跑几百个测试用例时泄漏会累积起来最终可能导致内存不足。我一般会在返回结果之前把哈希表整张释放掉void freeTable(Node** buckets, int size) { for (int i 0; i size; i) { Node* cur buckets[i]; while (cur ! NULL) { Node* tmp cur; cur cur-next; free(tmp); } } free(buckets); }每个链表节点都要单独释放最后释放桶数组本身。这个过程虽然麻烦但能帮你养成一个好习惯每次malloc都和free配对出现。实际工程中内存泄漏是非常隐蔽的bug从刷题开始就养成规范意识后面写项目时能少掉很多头发。4. 完整可提交的C代码一次遍历版twoSum4.1 代码全文把上面的组件拼起来再加上twoSum主体逻辑就是一份可以直接提交到LeetCode的完整代码#include stdlib.h #include string.h typedef struct Node { int key; int val; struct Node* next; } Node; int hash(int key, int size) { if (key 0) { return (key % size size) % size; } return key % size; } void insert(Node** buckets, int size, int key, int val) { int index hash(key, size); Node* newNode (Node*)malloc(sizeof(Node)); newNode-key key; newNode-val val; newNode-next buckets[index]; buckets[index] newNode; } int find(Node** buckets, int size, int key, int* foundVal) { int index hash(key, size); Node* cur buckets[index]; while (cur ! NULL) { if (cur-key key) { *foundVal cur-val; return 1; } cur cur-next; } return 0; } void freeTable(Node** buckets, int size) { for (int i 0; i size; i) { Node* cur buckets[i]; while (cur ! NULL) { Node* tmp cur; cur cur-next; free(tmp); } } free(buckets); } int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int tableSize numsSize * 2; Node** buckets (Node**)calloc(tableSize, sizeof(Node*)); for (int i 0; i numsSize; i) { int complement target - nums[i]; int foundVal; if (find(buckets, tableSize, complement, foundVal)) { int* result (int*)malloc(2 * sizeof(int)); result[0] foundVal; result[1] i; *returnSize 2; freeTable(buckets, tableSize); return result; } insert(buckets, tableSize, nums[i], i); } freeTable(buckets, tableSize); *returnSize 0; return NULL; }4.2 逐步拆解主体逻辑这段twoSum的核心流程就是前面讲的边遍历边查找边插入tableSize numsSize * 2桶数组长度取数组长度的两倍保证装填因子不超过 0.5冲突很少calloc(tableSize, sizeof(Node*))calloc会把内存清零也就是把所有桶初始化为 NULL这一步很省心遍历到nums[i]时先算complement target - nums[i]然后到哈希表里查找找到就分配结果数组并填好下标然后释放哈希表返回结果没找到就执行insert把当前元素存入哈希表继续循环如果循环走完还没找到按题目的约束不会发生释放资源后返回 NULL并设置*returnSize 0每一步的顺序都是精心安排过的先查再插保证了不可能出现同一个元素和自己匹配的情况。4.3 边界条件与隐藏细节C语言的题解里最容易翻车的不是算法思路而是内存和指针的边角细节。以下几个点是我反复踩过、后来形成肌肉记忆的地方结果数组必须用 malloc 分配。C语言函数里如果返回一个局部数组的首地址函数结束后栈帧被回收这个指针就成了悬垂指针。LeetCode的判题系统读到的是垃圾数据程序行为不可预测。*returnSize一定要赋值。如果你忘了设置它判题系统就不知道返回数组有多长可能会越界读取内存。哪怕返回 NULL也要把*returnSize设为 0。负数的哈希处理。上面用的是两次取模方式比较稳妥。有些题解用abs(key) % size一般情况下没问题但要意识到abs的边界风险。calloc和malloc memset是等价的。我选择calloc纯粹是可以少写一行初始化代码。如果要用malloc必须立刻补一句memset(buckets, 0, sizeof(Node*) * tableSize)。5. 我在LeetCode上反复提交时踩过的坑5.1 哈希桶初始化遗漏野指针崩溃现场有一段时间我写C语言代码图省事初始化哈希表时用了malloc却忘记清零直接在后面插入节点。结果程序运行到链表遍历时访问了一个完全随机的地址直接段错误。排查了很久才意识到malloc返回的内存是不确定的内容它不会自动替你清零。所以桶数组初始状态可能是一些乱七八糟的垃圾指针。你往链表头部插入节点时newNode-next buckets[index]就把这个垃圾地址挂到了链表上。等到查找时遍历链表程序就会按垃圾地址去访问内存崩溃是必然的。后来我强制自己遵守一个规则只要分配了哈希桶数组下一步必做清零操作。用calloc也好用memset也好总之这一步不能省。5.2 内存释放顺序搞反先释放桶数组再释放链表节点还有一个我犯过不止一次的错释放哈希表时先free(buckets)再想着去释放链表节点。这完全把顺序搞反了——桶数组都没了链表头指针从哪来程序在第二次释放时就会访问已释放的内存。正确的顺序一定是先遍历所有桶把每个桶下面的链表节点逐个释放干净最后再释放桶数组本身。也就是我前面freeTable里的顺序。实在记不住的话可以想象成拆房子得先搬走屋里的家具才能拆承重墙最后拆除大楼的立柱。5.3 哈希函数负数取模踩坑下标变成负数LeetCode的两数之和题目里nums中的元素是允许出现负数的。我第一次提交的哈希函数是这样写的int hash(int key, int size) { return key % size; }当时数组里碰巧全是正数测试样例都过了。后来我换了一套包含负数的测试数据程序直接数组越界判题系统报了 Runtime Error。原因前面提到过C语言的求余运算在处理负数时结果可能是负数。-3 % 5在C语言里等于-3如果你拿这个当数组下标当然越界。从那之后我的哈希函数就固定成了(key % size size) % size这种写法不为别的就为稳妥。5.4 返回值里下标顺序不一致导致提交失败还有一次提交失败不是因为算法错而是因为返回的[j, i]顺序和请求的下标顺序不一致。详情记不太清了只记得最后是通过仔细读题才发现的。这里给大家的提醒是LeetCode对返回的两个下标要求是可以乱序的你的代码里先找到哪个下标就把哪个放前面这个完全由自己控制但要保证最终返回的两个值确实来自两个不同的数组位置。我在代码里习惯先返回之前存进哈希表的下标foundVal再返回当前遍历到的下标i。这个顺序写清楚后就没有再出过类似问题。5.5 LeetCode判题环境中的内存泄漏问题可能很多人觉得LeetCode跑完一个测试用例就会回收内存不释放也没关系。但我在刷题时遇到过个别题目如果每次调用都泄漏一点内存多次调用之后程序会变得异常慢甚至崩溃。LeetCode的判题常常会用一个进程连续调用你的函数多次。twoSum这种函数每调用一次哈希表就泄漏一次。虽然单次量很小但如果测试用例有几万个那泄漏的内存就会非常可观。因此哪怕LeetCode不报错我也会在返回之前释放掉所有动态分配的内存。这是代码洁癖更是工程素养。6. 这道题之外哈希表的变体和后续刷题方向6.1 从Two Sum到Three Sum哈希表还管用吗很多人在做完两数之和后会自然地想三数之和是不是也能用哈希表结论是可以但一般不建议这么做。Three Sum 的经典解法是排序 双指针时间复杂度 O(n²)如果硬要用哈希表去重问题会非常麻烦。但哈希表思想在两数之和的变体题目中依然非常实用比如LeetCode 167. Two Sum II - Input Array Is Sorted数组有序可以用双指针也可以用哈希表LeetCode 1. 这道题的多个版本HashMap存储值到下标的映射的通用模板可以套到很多题目里我的建议是两数之和用哈希表三数之和用排序双指针四数之和则需要双指针加一层循环或者用哈希表辅助。不同的题目有不同最适合的解法这个需要自己在刷题中慢慢积累感觉。6.2 哈希表在LeetCode高频题中的位置哈希表绝不只是为这道题准备的。我简单梳理了一下LeetCode上高频考察哈希表的题型供你做一个后续刷题计划题目难度哈希表的作用1. Two SumEasy值到下标的映射O(1)查找补数387. First Unique Character in a StringEasy统计字符出现次数242. Valid AnagramEasy统计字符频率做对比49. Group AnagramsMedium排序后的字符串作为哈希表key3. Longest Substring Without Repeating CharactersMedium记录字符最后一次出现的位置560. Subarray Sum Equals KMedium前缀和 哈希表非常经典128. Longest Consecutive SequenceMedium用哈希集合判断连续序列的起点其中 560 题是我个人认为最能体现哈希表空间换时间威力的题目强烈推荐在掌握本题之后去挑战一下。6.3 学习建议C语言刷题到底值不值得这个问题我经常被问到。说实话如果你现在时间紧迫、面试在即用C或Python刷题效率绝对更高因为内置的哈希表可以随手调用。但如果你是想扎实地打数据结构基本功那我非常推荐用C语言过一遍简单题和中等题。原因很简单高级语言把哈希表的复杂度封装在标准库里你调用时只能感受到快感受不到为什么快。而手写一遍哈希表后你会彻底理解key通过哈希函数映射到桶下标冲突时链地址法如何工作为什么查找平均 O(1)这些概念。以后再回头看 C 的unordered_map或者 Python 的dict你会觉得它们就是封装好的同一套东西。我的个人经验是用C语言刷题的前一百道会非常痛苦因为每个基础数据结构都要自己造轮子光是链表、哈希表、栈、队列这四件套就能写几百行代码。但一旦熬过去这个阶段后续面对任何算法题时你对底层发生了什么是有画面感的。这种底层认知是刷多少道调用API的题都换不来的。结尾从两数之和这道题延伸出去我最大的体会是算法题最值钱的不是答案而是你在写答案过程中建立起来的底层直觉。我第一次看到哈希表时也是一头雾水——为什么要额外开一块内存为什么取模能定位到桶直到自己动手把链地址法一个节点一个节点地串起来这些疑问才真正消失。如果你也是C语言初学者被这道题的代码量吓到了别灰心。这些结构体、哈希函数、内存释放的模板每多写一次就熟练一分。先把这道题的完整代码在自己机器上跑通再亲手把哈希表清空函数加上动手敲一遍比看十遍题解都有用。等你把这道题彻底吃透再回头看LeetCode top 100里那些考哈希表的中等题会觉得心里有底很多。