你可能会觉得奇怪力扣第一题“两数之和”已经被全网讲烂了还有什么好写的但作为一个用C语言刷题的人我对这道题的情绪其实很复杂。它挂着“简单”的标签可C语言新手第一次进来往往会卡在三个地方不懂函数签名里returnSize是干嘛的、不知道为什么返回值得用malloc、想用哈希表结果发现标准库根本没有。你去看题解Java随手一个HashMapPython一个字典到了C语言这里要么劝你直接用暴力要么甩给你一大坨手写的结构体。这篇文章我想把这个过程彻底讲透从暴力版的边界推导到手写开放寻址哈希表的每个细节再到提交经常踩的坑一条线走通希望看完你也能一次性AC。1. 开跑前先把力扣的函数签名读明白1.1 四个参数到底在说什么力扣的C语言题和咱们平时写的程序有个很大区别没有标准输入输出判题器直接调用你提交的这个函数然后根据返回值判断对错。“两数之和”的函数签名是int* twoSum(int* nums, int numsSize, int target, int* returnSize)很多人第一次写的时候盯着这个签名看了半天为什么返回值是int*为什么还要单独传一个returnSize指针原因是C语言函数只能返回一个值而“两数之和”的结果天然有两个维度一个是返回数组的起始地址一个是数组的长度。你可以用结构体把这两个打包返回但力扣的判题接口已经定死了所以长度信息必须通过指针参数传出来。returnSize就是干这个的你在函数里找到答案后要做两件事把下标数组的首地址返回同时把*returnSize赋值为2。如果没找到按约定把*returnSize赋值为0返回NULL。我见过很多新手在编辑器里手写这道题时函数写成了int* twoSum(int* nums, int numsSize, int target)少了returnSize。这种老签名在一些早期题解里确实出现过力扣后来统一改了接口。如果你照着老写法提交编译会直接报错因为符号对不上。所以第一步先把当前版本的签名背下来这是整个题解的地基。1.2 为什么返回值必须用mallocint*返回值另一个容易踩的坑是返回了局部数组的地址。很多人写完暴力循环顺手这么写int result[2]; result[0] i; result[1] j; return result;编译能过运行结果却可能是一堆乱码。原因在于result是函数栈上的局部数组函数一返回这块内存就失效了。判题器再来读这块地址拿到的内容完全不可预期甚至可能触发段错误。正确做法是使用malloc在堆上申请两块int空间int* result (int*)malloc(sizeof(int) * 2); if (result NULL) { *returnSize 0; return NULL; }这样函数返回后内存仍然有效。C语言里数组不是一等公民没有自动生命周期这也是为什么同样一道题Java和Python选手可以一句return new int[]{i, j};或者return [i, j]了事C语言必须自己管内存。这道题对你的第一个训练就是“返回动态内存”这件事本身。1.3 本地调试外壳怎么搭力扣的编辑器里只有函数体没法直接printf看结果。我建议你本地建一个测试外壳把函数和main放在同一个文件里自己造数据验证。大致的结构是#include stdio.h #include stdlib.h // 这里放 twoSum 的实现 int main(void) { int nums[] {2, 7, 11, 15}; int returnSize 0; int* res twoSum(nums, 4, 9, returnSize); if (res ! NULL) { printf([%d, %d]\n, res[0], res[1]); free(res); } return 0; }这一步看起来简单但重要性被严重低估。我刷题前两年的习惯是直接在线提交错了就在那个小框里改效率很低。后来养成了本地调试的习惯很多问题比如数组越界、返回值错误、内存泄漏用本地编译器加调试器几分钟就能定位。VS Code用户配置好gcc之后跑这种单文件C代码非常方便强烈建议不要在网页上裸写裸调。2. 先写能过的暴力版C语言的一力降十会2.1 双重循环的边界推导暴力解法思路直接到不需要解释从第0个元素开始每次和它后面的所有元素逐一相加看是否等于target。代码写出来是这样int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* result (int*)malloc(sizeof(int) * 2); if (result NULL) { *returnSize 0; return NULL; } for (int i 0; i numsSize - 1; 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; free(result); return NULL; }我重点说一下i numsSize - 1这个边界。因为内层循环j从i 1开始所以当i numsSize - 1时内层根本不会执行循环白白多跑一轮虽然不影响正确性但看起来不够严谨。写成i numsSize - 1含义是“我要跟后面的元素配对所以最后一个元素不可能当左指针”。内层j i 1则避免了两类问题一是避免了元素和自身配对二是省掉了一半的重复计算。(i, j)和(j, i)是同一对下标从i 1开始天然只遍历一次。如果你写成j 0那么当nums[i] * 2 target时会误判成同一个元素用了两次这是这道题非常经典的错误。2.2 暴力版在C语言里其实一点也不难看先说个大实话这道题在LeetCode上用C语言写暴力版是能过的。题目给的数据范围是2 nums.length 10^4双层循环最坏情况是大约5*10^7次加法比较。对于现代CPU上的C语言编译产物来说这个量级通常几百毫秒内就能跑完力扣的判题机又不会卡得特别死所以AC问题不大。这和Python选手的情况完全不同。Python本身是解释型语言写过同样的双层循环在数据量大时经常会超时所以Python选手必须更早考虑哈希表。而C语言因为执行效率高在一道n 10^4的题目里暴力确实是“一力降十会”。我们不需要对暴力解法产生某种羞耻感能用最小代码量解决本身就是一种工程能力。但注意“能过”是有前提的如果numsSize到10^5甚至10^6暴力会瞬间变成约10^9到10^12次操作这时候就不可能过了。所以这道题真正的分水岭不是“你写不写得出暴力”而是“你知道什么时候该放弃暴力”。2.3 暴力版的复杂度真相与适用场景暴力解法的时间和空间复杂度分别是O(n^2)和O(1)。它最大的优势是代码短、逻辑直白、不容易写错、不需要额外内存。在很多实际工程项目里如果确认了输入规模很小或者target出现的概率很高导致循环几乎不会跑满暴力反而是最稳的选择。但力扣题核心考的不是“能跑”而是“在复杂度上不丢分”。面试官看到你提交暴力代码大概率会追问一句“能不能优化到O(n)”这时候你再开始讲哈希表才有“先暴力后优化”的完整故事线。所以我的建议是在自己学习的时候两种解法都要写但是提交顺序可以先暴力后哈希体会一下性能差异。3. 哈希表解法从入门到能提交3.1 哈希表为什么能快一个数量级暴力的瓶颈在于对于每个元素nums[i]我们都要扫描后面的所有元素才知道target - nums[i]存不存在。如果能把这个“查找”操作的时间从O(n)变成O(1)总时间就是O(n)。哈希表就是干这个的。你可以把它理解成一本“带拼音索引的字典”你想找“刷”这个字不用从第一页翻到最后一页直接按拼音索引翻到对应区域一下就能定位。哈希表通过一个散列函数把元素的值映射到数组的一个下标上把“查找一个值”变成“去数组的某个位置看一眼”。C语言没有内置哈希表但自己实现一个够用的版本并不难。这道题我们只需要三个操作初始化、插入(key, value)、根据key查value。这里的key是数组元素的值value是元素的下标。3.2 手写一个够用的开放寻址哈希表我推荐用开放寻址法实现哈希表。整体思路是维护一个结构体数组每个槽位有三个字段key、value、used。used标记这个槽位有没有被占用这是关键因为C语言里没法靠key是否为0来判断槽位是否为空——数组元素的值完全可能是0。typedef struct { int key; int value; int used; } HashEntry; typedef struct { HashEntry* entries; int capacity; } HashMap;散列函数更简单直接对表长取模static int hashKey(int key, int capacity) { return ((key % capacity) capacity) % capacity; }这里用(key % capacity capacity) % capacity是为了处理负数。比如key -7C语言里-7 % 5的结果是-2直接当成数组下标就是负数越界。加上capacity再取模一次就保证结果落到[0, capacity - 1]区间。这个负数的坑我本来打算放到后面避坑章节再讲但因为它直接出现在哈希函数里必须先交代清楚。插入和查询都使用线性探测解决冲突。所谓冲突就是两个不同的key取模后落在同一个槽位。开放寻址法的做法是槽位被占了就往后顺延找下一个空位。static void put(HashMap* map, int key, int value) { int idx hashKey(key, map-capacity); while (map-entries[idx].used) { if (map-entries[idx].key key) { map-entries[idx].value value; return; } idx (idx 1) % map-capacity; } map-entries[idx].key key; map-entries[idx].value value; map-entries[idx].used 1; } static int get(HashMap* map, int key, int* found) { int idx hashKey(key, map-capacity); while (map-entries[idx].used) { if (map-entries[idx].key key) { *found 1; return map-entries[idx].value; } idx (idx 1) % map-capacity; } *found 0; return -1; }注意get函数里查找时遇到used 0的槽位就停下来说明后面不可能再有这个key了。这是开放寻址法在“只插入不删除”场景下的一个便利。如果允许删除元素就不能这么简单了需要引入“墓碑”标记否则会切断探测链导致后续查找失效。不过这道题不需要删除所以先不做扩展。3.3 先查再插顺序是整个算法的灵魂很多拿着哈希表思路写这道题的人第一次都这样写先把所有元素都插进去再遍历一遍数组对每个nums[i]去哈希表里查target - nums[i]。这个方案对多数测试用例都能过但会栽在一种特殊输入上数组里有重复元素且这两个重复元素的和正好等于target。比如nums [3, 3]target 6。正确结果应该是[0, 1]但如果你先把两个3都插到哈希表里由于key相同后插入的下标1会覆盖先插入的下标0。等你再查的时候哈希表里key 3对应的value是1结果你可能找到[1, 1]这种自引用组合或者因为查到的下标等于当前下标不得不做额外的特判。正确做法是边遍历边查边插。对当前元素nums[i]先去哈希表里查target - nums[i]有没有出现过。如果出现过说明之前某个元素和当前元素正好凑成目标值直接返回如果没出现过再把当前的nums[i]插入哈希表。按照这个顺序处理[3, 3]的过程是遍历到第二个3时哈希表里已经存了第一个3的下标0因为第一个3在遍历时先查后插已经被放进去了查询target - 3 3命中下标0输出[0, 1]完全正确。这里有一个可以深入理解的点为什么“先查”能保证两个下标不重复因为当前元素还没有插入表里所以查询到的任何下标都严格小于i必然来自之前的元素。这个约束是算法正确性的核心比任何特判都干净。3.4 完整可提交代码把上面的哈希表拼起来完整解法是这样的#include stdlib.h typedef struct { int key; int value; int used; } HashEntry; typedef struct { HashEntry* entries; int capacity; } HashMap; static int hashKey(int key, int capacity) { return ((key % capacity) capacity) % capacity; } static void initHashMap(HashMap* map, int capacity) { map-entries (HashEntry*)calloc(capacity, sizeof(HashEntry)); map-capacity capacity; } static void put(HashMap* map, int key, int value) { int idx hashKey(key, map-capacity); while (map-entries[idx].used) { if (map-entries[idx].key key) { map-entries[idx].value value; return; } idx (idx 1) % map-capacity; } map-entries[idx].key key; map-entries[idx].value value; map-entries[idx].used 1; } static int get(HashMap* map, int key, int* found) { int idx hashKey(key, map-capacity); while (map-entries[idx].used) { if (map-entries[idx].key key) { *found 1; return map-entries[idx].value; } idx (idx 1) % map-capacity; } *found 0; return -1; } static void freeHashMap(HashMap* map) { free(map-entries); map-entries NULL; map-capacity 0; } int* twoSum(int* nums, int numsSize, int target, int* returnSize) { if (numsSize 2) { *returnSize 0; return NULL; } HashMap map; initHashMap(map, numsSize * 2); int* result (int*)malloc(sizeof(int) * 2); if (result NULL) { freeHashMap(map); *returnSize 0; return NULL; } for (int i 0; i numsSize; i) { int found 0; int preIndex get(map, target - nums[i], found); if (found) { result[0] preIndex; result[1] i; *returnSize 2; freeHashMap(map); return result; } put(map, nums[i], i); } free(result); freeHashMap(map); *returnSize 0; return NULL; }容量取numsSize * 2是把负载因子压到了0.5以下。负载因子是哈希表里已存元素个数和表长的比值开放寻址法下负载因子越小冲突概率越低线性探测链越短。numsSize * 2在绝大多数情况下足够安全。为什么要单独给哈希表分配一块内存因为数组可能很长每个查找都走一次线性探测如果表太小冲突堆积会让“平均O(1)”退化成“最坏O(n)”。开两倍空间本质是在空间和冲突概率之间取一个工程上合理的平衡点。4. 提交过不了的五个真实原因4.1 第一个坑returnSize没赋值returnSize是判题器判断结果长度的依据。如果你找到了答案只把数组地址返回忘记给*returnSize赋值判题器拿到的可能是栈上的随机值轻则输出异常重则越界读取。这个错误在“只跑本地printf”的测试里很难被发现因为你自己打印结果时根本不看returnSize但力扣判题器会看。我的习惯是在函数入口处先给*returnSize 0后续每次成功返回之前再显式设置成2。这样即使哪里写漏了也至少有个安全值。无解时返回NULL并把returnSize置0是力扣C语言接口的通用约定养成习惯对后面所有数组类题目都有好处。4.2 第二个坑负数取模和整数溢出C语言的取模运算在操作数有负数时结果符号和被除数相同。-7 % 5在C99标准下是-2而不是2。所以直接用key % capacity当下标会越界。哈希函数里那句(key % capacity capacity) % capacity就是专门用来把负数结果拉回正数区间的。另一个隐藏问题是加法溢出。nums[i] nums[j]在暴力解法里如果数组元素是INT_MAX级别的数相加会溢出成负数导致明明不相等的两个数因为溢出反而“相等”了。力扣这道题的数据范围一般不会触到这个边界但严谨起见可以把比较改成nums[i] target - nums[j]避免先加后比。这也是很多工程编码规范里推荐的做法“把可能溢出的运算转换成减法”。4.3 第三个坑重复元素[3,3]的时序前面在3.3节已经讲过先查再插的原理这里再补一个细节为什么很多Java题解里用“先全部插入再查找”也能过因为他们通常会在查到结果后加一句if (map.get(nums[i]) i) continue;之类的自引用判断。这种判断属于事后补救逻辑上绕了一圈。C语言版本如果照搬这个思路不仅代码变长还要额外处理哈希表里相同key的覆盖问题容易越写越乱。所以直接用“边查边插”从源头规避这才是正解。4.4 第四个坑扩容与负载因子力扣这道题不需要扩容因为我们是先知道数据量的。但如果你把这个手写哈希表搬到其他场景比如动态读入数据就必须考虑扩容问题。开放寻址法的通用做法是当used数量超过容量的70%时申请一个两倍大的新表把所有旧元素重新哈希一遍。为什么必须重新哈希因为散列函数是key % capacity表长变了同一个key算出来的槽位也会变。直接搬数组会导致新表里的位置错乱查找时完全找不到。这个知识点在很多面试题里会以“设计一个HashMap”的形式出现提前在这里理解“为什么扩容要rehash”比背八股文有用得多。4.5 第五个坑free的强迫症检查清单C语言版本另一个容易出问题的点是内存管理。我见过有人在本地调试时twoSum返回后又free了一次结果double free程序直接崩。也看到过返回前忘了freeHashMap导致每次调用泄漏一大块内存。我的检查清单是malloc申请的结果数组在函数退出前要么作为返回值交出去要么free掉不能漏。哈希表内部用calloc申请的entries在函数退出前必须free不管是命中路径还是无解路径。free之后指针置NULL防止后续误用。调用方拿到返回值后用完记得free。本地可以用Valgrind跑一下输出最后一行只要有All heap blocks were freed -- no leaks are possible就可以放心提交。5. 从两数之和带出的三道变体题5.1 有序数组双指针把空间复杂度压到O(1)“两数之和”本身有个升级版如果输入数组是升序排列的比如力扣167题最优解就不再是哈希表而是双指针。初始化左指针left 0右指针right numsSize - 1。如果nums[left] nums[right] target直接返回如果和大于target说明右指针指向的数太大右指针左移如果和小于target说明左指针指向的数太小左指针右移。为什么这个算法不会漏解你可以这样理解数组有序那么nums[left] nums[right]决定了当前“搜索空间”的边界。当和太大时任何比右指针更靠右的元素都不可能让和变小所以右指针只能左移反之亦然。每一步都排除一整行或一整列时间复杂度O(n)空间复杂度O(1)比哈希表更省。从这道题到167题核心变化是“利用有序性”。面试时如果拿到的是有序数组而你还在写哈希表大概率会被追问一句“有没有更省空间的做法”。所以刷题时一定得把这两题放在一起看。5.2 不允许额外空间排序加二分还有一种变体要求不开额外空间但数组是乱序的哈希表不能用这时只能先排序再对每个元素二分查找target - nums[i]。排序成本是O(n log n)查找成本是O(n log n)。这个方案的代价是排序会改变元素顺序如果你需要返回原数组的下标就必须额外保存原始下标或者用结构体把值和下标绑在一起再排序。很多人在这一步卡住是因为排序后下标丢了。实际工程里我们经常用“索引数组”或“结构体数组”解决这类问题这也算一个很通用的建模技巧。5.3 从两数之和到三数之和思维升级的套路有了两数之和的基础三数之和就顺理成章了先排序固定第一个数剩下的两个数用双指针去找并注意跳过重复元素。四数之和再多套一层循环。你会发现两数之和里的“先查再插”思想到了三数之和里变成了“排序加双指针”哈希表反而不是最优解了因为去重逻辑会很麻烦。力扣热题100里围绕这个思路串起来的好几道题都值得做167两数之和II、15三数之和、18四数之和甚至还有“最接近的三数之和”。刷完这一串你会发现两数之和教的不是那个函数怎么写而是一整套“如何从暴力到优化”的思维路径。我在实际刷题中的感受是第一题的价值不在于“AC”而在于它逼着你把C语言的内存管理、返回值约定、手写数据结构这些基本功过了一遍。你把这套东西彻底搞明白后面再刷数组、链表、哈希表相关的题目都会顺畅很多。至少当你在力扣热题100里刷到中后段回头看到这道被标记为“简单”的第一题时你会真心觉得它其实是C语言新手的一座分水岭。 C语言实现两数之和：从暴力到手写哈希表全解析
你可能会觉得奇怪力扣第一题“两数之和”已经被全网讲烂了还有什么好写的但作为一个用C语言刷题的人我对这道题的情绪其实很复杂。它挂着“简单”的标签可C语言新手第一次进来往往会卡在三个地方不懂函数签名里returnSize是干嘛的、不知道为什么返回值得用malloc、想用哈希表结果发现标准库根本没有。你去看题解Java随手一个HashMapPython一个字典到了C语言这里要么劝你直接用暴力要么甩给你一大坨手写的结构体。这篇文章我想把这个过程彻底讲透从暴力版的边界推导到手写开放寻址哈希表的每个细节再到提交经常踩的坑一条线走通希望看完你也能一次性AC。1. 开跑前先把力扣的函数签名读明白1.1 四个参数到底在说什么力扣的C语言题和咱们平时写的程序有个很大区别没有标准输入输出判题器直接调用你提交的这个函数然后根据返回值判断对错。“两数之和”的函数签名是int* twoSum(int* nums, int numsSize, int target, int* returnSize)很多人第一次写的时候盯着这个签名看了半天为什么返回值是int*为什么还要单独传一个returnSize指针原因是C语言函数只能返回一个值而“两数之和”的结果天然有两个维度一个是返回数组的起始地址一个是数组的长度。你可以用结构体把这两个打包返回但力扣的判题接口已经定死了所以长度信息必须通过指针参数传出来。returnSize就是干这个的你在函数里找到答案后要做两件事把下标数组的首地址返回同时把*returnSize赋值为2。如果没找到按约定把*returnSize赋值为0返回NULL。我见过很多新手在编辑器里手写这道题时函数写成了int* twoSum(int* nums, int numsSize, int target)少了returnSize。这种老签名在一些早期题解里确实出现过力扣后来统一改了接口。如果你照着老写法提交编译会直接报错因为符号对不上。所以第一步先把当前版本的签名背下来这是整个题解的地基。1.2 为什么返回值必须用mallocint*返回值另一个容易踩的坑是返回了局部数组的地址。很多人写完暴力循环顺手这么写int result[2]; result[0] i; result[1] j; return result;编译能过运行结果却可能是一堆乱码。原因在于result是函数栈上的局部数组函数一返回这块内存就失效了。判题器再来读这块地址拿到的内容完全不可预期甚至可能触发段错误。正确做法是使用malloc在堆上申请两块int空间int* result (int*)malloc(sizeof(int) * 2); if (result NULL) { *returnSize 0; return NULL; }这样函数返回后内存仍然有效。C语言里数组不是一等公民没有自动生命周期这也是为什么同样一道题Java和Python选手可以一句return new int[]{i, j};或者return [i, j]了事C语言必须自己管内存。这道题对你的第一个训练就是“返回动态内存”这件事本身。1.3 本地调试外壳怎么搭力扣的编辑器里只有函数体没法直接printf看结果。我建议你本地建一个测试外壳把函数和main放在同一个文件里自己造数据验证。大致的结构是#include stdio.h #include stdlib.h // 这里放 twoSum 的实现 int main(void) { int nums[] {2, 7, 11, 15}; int returnSize 0; int* res twoSum(nums, 4, 9, returnSize); if (res ! NULL) { printf([%d, %d]\n, res[0], res[1]); free(res); } return 0; }这一步看起来简单但重要性被严重低估。我刷题前两年的习惯是直接在线提交错了就在那个小框里改效率很低。后来养成了本地调试的习惯很多问题比如数组越界、返回值错误、内存泄漏用本地编译器加调试器几分钟就能定位。VS Code用户配置好gcc之后跑这种单文件C代码非常方便强烈建议不要在网页上裸写裸调。2. 先写能过的暴力版C语言的一力降十会2.1 双重循环的边界推导暴力解法思路直接到不需要解释从第0个元素开始每次和它后面的所有元素逐一相加看是否等于target。代码写出来是这样int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* result (int*)malloc(sizeof(int) * 2); if (result NULL) { *returnSize 0; return NULL; } for (int i 0; i numsSize - 1; 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; free(result); return NULL; }我重点说一下i numsSize - 1这个边界。因为内层循环j从i 1开始所以当i numsSize - 1时内层根本不会执行循环白白多跑一轮虽然不影响正确性但看起来不够严谨。写成i numsSize - 1含义是“我要跟后面的元素配对所以最后一个元素不可能当左指针”。内层j i 1则避免了两类问题一是避免了元素和自身配对二是省掉了一半的重复计算。(i, j)和(j, i)是同一对下标从i 1开始天然只遍历一次。如果你写成j 0那么当nums[i] * 2 target时会误判成同一个元素用了两次这是这道题非常经典的错误。2.2 暴力版在C语言里其实一点也不难看先说个大实话这道题在LeetCode上用C语言写暴力版是能过的。题目给的数据范围是2 nums.length 10^4双层循环最坏情况是大约5*10^7次加法比较。对于现代CPU上的C语言编译产物来说这个量级通常几百毫秒内就能跑完力扣的判题机又不会卡得特别死所以AC问题不大。这和Python选手的情况完全不同。Python本身是解释型语言写过同样的双层循环在数据量大时经常会超时所以Python选手必须更早考虑哈希表。而C语言因为执行效率高在一道n 10^4的题目里暴力确实是“一力降十会”。我们不需要对暴力解法产生某种羞耻感能用最小代码量解决本身就是一种工程能力。但注意“能过”是有前提的如果numsSize到10^5甚至10^6暴力会瞬间变成约10^9到10^12次操作这时候就不可能过了。所以这道题真正的分水岭不是“你写不写得出暴力”而是“你知道什么时候该放弃暴力”。2.3 暴力版的复杂度真相与适用场景暴力解法的时间和空间复杂度分别是O(n^2)和O(1)。它最大的优势是代码短、逻辑直白、不容易写错、不需要额外内存。在很多实际工程项目里如果确认了输入规模很小或者target出现的概率很高导致循环几乎不会跑满暴力反而是最稳的选择。但力扣题核心考的不是“能跑”而是“在复杂度上不丢分”。面试官看到你提交暴力代码大概率会追问一句“能不能优化到O(n)”这时候你再开始讲哈希表才有“先暴力后优化”的完整故事线。所以我的建议是在自己学习的时候两种解法都要写但是提交顺序可以先暴力后哈希体会一下性能差异。3. 哈希表解法从入门到能提交3.1 哈希表为什么能快一个数量级暴力的瓶颈在于对于每个元素nums[i]我们都要扫描后面的所有元素才知道target - nums[i]存不存在。如果能把这个“查找”操作的时间从O(n)变成O(1)总时间就是O(n)。哈希表就是干这个的。你可以把它理解成一本“带拼音索引的字典”你想找“刷”这个字不用从第一页翻到最后一页直接按拼音索引翻到对应区域一下就能定位。哈希表通过一个散列函数把元素的值映射到数组的一个下标上把“查找一个值”变成“去数组的某个位置看一眼”。C语言没有内置哈希表但自己实现一个够用的版本并不难。这道题我们只需要三个操作初始化、插入(key, value)、根据key查value。这里的key是数组元素的值value是元素的下标。3.2 手写一个够用的开放寻址哈希表我推荐用开放寻址法实现哈希表。整体思路是维护一个结构体数组每个槽位有三个字段key、value、used。used标记这个槽位有没有被占用这是关键因为C语言里没法靠key是否为0来判断槽位是否为空——数组元素的值完全可能是0。typedef struct { int key; int value; int used; } HashEntry; typedef struct { HashEntry* entries; int capacity; } HashMap;散列函数更简单直接对表长取模static int hashKey(int key, int capacity) { return ((key % capacity) capacity) % capacity; }这里用(key % capacity capacity) % capacity是为了处理负数。比如key -7C语言里-7 % 5的结果是-2直接当成数组下标就是负数越界。加上capacity再取模一次就保证结果落到[0, capacity - 1]区间。这个负数的坑我本来打算放到后面避坑章节再讲但因为它直接出现在哈希函数里必须先交代清楚。插入和查询都使用线性探测解决冲突。所谓冲突就是两个不同的key取模后落在同一个槽位。开放寻址法的做法是槽位被占了就往后顺延找下一个空位。static void put(HashMap* map, int key, int value) { int idx hashKey(key, map-capacity); while (map-entries[idx].used) { if (map-entries[idx].key key) { map-entries[idx].value value; return; } idx (idx 1) % map-capacity; } map-entries[idx].key key; map-entries[idx].value value; map-entries[idx].used 1; } static int get(HashMap* map, int key, int* found) { int idx hashKey(key, map-capacity); while (map-entries[idx].used) { if (map-entries[idx].key key) { *found 1; return map-entries[idx].value; } idx (idx 1) % map-capacity; } *found 0; return -1; }注意get函数里查找时遇到used 0的槽位就停下来说明后面不可能再有这个key了。这是开放寻址法在“只插入不删除”场景下的一个便利。如果允许删除元素就不能这么简单了需要引入“墓碑”标记否则会切断探测链导致后续查找失效。不过这道题不需要删除所以先不做扩展。3.3 先查再插顺序是整个算法的灵魂很多拿着哈希表思路写这道题的人第一次都这样写先把所有元素都插进去再遍历一遍数组对每个nums[i]去哈希表里查target - nums[i]。这个方案对多数测试用例都能过但会栽在一种特殊输入上数组里有重复元素且这两个重复元素的和正好等于target。比如nums [3, 3]target 6。正确结果应该是[0, 1]但如果你先把两个3都插到哈希表里由于key相同后插入的下标1会覆盖先插入的下标0。等你再查的时候哈希表里key 3对应的value是1结果你可能找到[1, 1]这种自引用组合或者因为查到的下标等于当前下标不得不做额外的特判。正确做法是边遍历边查边插。对当前元素nums[i]先去哈希表里查target - nums[i]有没有出现过。如果出现过说明之前某个元素和当前元素正好凑成目标值直接返回如果没出现过再把当前的nums[i]插入哈希表。按照这个顺序处理[3, 3]的过程是遍历到第二个3时哈希表里已经存了第一个3的下标0因为第一个3在遍历时先查后插已经被放进去了查询target - 3 3命中下标0输出[0, 1]完全正确。这里有一个可以深入理解的点为什么“先查”能保证两个下标不重复因为当前元素还没有插入表里所以查询到的任何下标都严格小于i必然来自之前的元素。这个约束是算法正确性的核心比任何特判都干净。3.4 完整可提交代码把上面的哈希表拼起来完整解法是这样的#include stdlib.h typedef struct { int key; int value; int used; } HashEntry; typedef struct { HashEntry* entries; int capacity; } HashMap; static int hashKey(int key, int capacity) { return ((key % capacity) capacity) % capacity; } static void initHashMap(HashMap* map, int capacity) { map-entries (HashEntry*)calloc(capacity, sizeof(HashEntry)); map-capacity capacity; } static void put(HashMap* map, int key, int value) { int idx hashKey(key, map-capacity); while (map-entries[idx].used) { if (map-entries[idx].key key) { map-entries[idx].value value; return; } idx (idx 1) % map-capacity; } map-entries[idx].key key; map-entries[idx].value value; map-entries[idx].used 1; } static int get(HashMap* map, int key, int* found) { int idx hashKey(key, map-capacity); while (map-entries[idx].used) { if (map-entries[idx].key key) { *found 1; return map-entries[idx].value; } idx (idx 1) % map-capacity; } *found 0; return -1; } static void freeHashMap(HashMap* map) { free(map-entries); map-entries NULL; map-capacity 0; } int* twoSum(int* nums, int numsSize, int target, int* returnSize) { if (numsSize 2) { *returnSize 0; return NULL; } HashMap map; initHashMap(map, numsSize * 2); int* result (int*)malloc(sizeof(int) * 2); if (result NULL) { freeHashMap(map); *returnSize 0; return NULL; } for (int i 0; i numsSize; i) { int found 0; int preIndex get(map, target - nums[i], found); if (found) { result[0] preIndex; result[1] i; *returnSize 2; freeHashMap(map); return result; } put(map, nums[i], i); } free(result); freeHashMap(map); *returnSize 0; return NULL; }容量取numsSize * 2是把负载因子压到了0.5以下。负载因子是哈希表里已存元素个数和表长的比值开放寻址法下负载因子越小冲突概率越低线性探测链越短。numsSize * 2在绝大多数情况下足够安全。为什么要单独给哈希表分配一块内存因为数组可能很长每个查找都走一次线性探测如果表太小冲突堆积会让“平均O(1)”退化成“最坏O(n)”。开两倍空间本质是在空间和冲突概率之间取一个工程上合理的平衡点。4. 提交过不了的五个真实原因4.1 第一个坑returnSize没赋值returnSize是判题器判断结果长度的依据。如果你找到了答案只把数组地址返回忘记给*returnSize赋值判题器拿到的可能是栈上的随机值轻则输出异常重则越界读取。这个错误在“只跑本地printf”的测试里很难被发现因为你自己打印结果时根本不看returnSize但力扣判题器会看。我的习惯是在函数入口处先给*returnSize 0后续每次成功返回之前再显式设置成2。这样即使哪里写漏了也至少有个安全值。无解时返回NULL并把returnSize置0是力扣C语言接口的通用约定养成习惯对后面所有数组类题目都有好处。4.2 第二个坑负数取模和整数溢出C语言的取模运算在操作数有负数时结果符号和被除数相同。-7 % 5在C99标准下是-2而不是2。所以直接用key % capacity当下标会越界。哈希函数里那句(key % capacity capacity) % capacity就是专门用来把负数结果拉回正数区间的。另一个隐藏问题是加法溢出。nums[i] nums[j]在暴力解法里如果数组元素是INT_MAX级别的数相加会溢出成负数导致明明不相等的两个数因为溢出反而“相等”了。力扣这道题的数据范围一般不会触到这个边界但严谨起见可以把比较改成nums[i] target - nums[j]避免先加后比。这也是很多工程编码规范里推荐的做法“把可能溢出的运算转换成减法”。4.3 第三个坑重复元素[3,3]的时序前面在3.3节已经讲过先查再插的原理这里再补一个细节为什么很多Java题解里用“先全部插入再查找”也能过因为他们通常会在查到结果后加一句if (map.get(nums[i]) i) continue;之类的自引用判断。这种判断属于事后补救逻辑上绕了一圈。C语言版本如果照搬这个思路不仅代码变长还要额外处理哈希表里相同key的覆盖问题容易越写越乱。所以直接用“边查边插”从源头规避这才是正解。4.4 第四个坑扩容与负载因子力扣这道题不需要扩容因为我们是先知道数据量的。但如果你把这个手写哈希表搬到其他场景比如动态读入数据就必须考虑扩容问题。开放寻址法的通用做法是当used数量超过容量的70%时申请一个两倍大的新表把所有旧元素重新哈希一遍。为什么必须重新哈希因为散列函数是key % capacity表长变了同一个key算出来的槽位也会变。直接搬数组会导致新表里的位置错乱查找时完全找不到。这个知识点在很多面试题里会以“设计一个HashMap”的形式出现提前在这里理解“为什么扩容要rehash”比背八股文有用得多。4.5 第五个坑free的强迫症检查清单C语言版本另一个容易出问题的点是内存管理。我见过有人在本地调试时twoSum返回后又free了一次结果double free程序直接崩。也看到过返回前忘了freeHashMap导致每次调用泄漏一大块内存。我的检查清单是malloc申请的结果数组在函数退出前要么作为返回值交出去要么free掉不能漏。哈希表内部用calloc申请的entries在函数退出前必须free不管是命中路径还是无解路径。free之后指针置NULL防止后续误用。调用方拿到返回值后用完记得free。本地可以用Valgrind跑一下输出最后一行只要有All heap blocks were freed -- no leaks are possible就可以放心提交。5. 从两数之和带出的三道变体题5.1 有序数组双指针把空间复杂度压到O(1)“两数之和”本身有个升级版如果输入数组是升序排列的比如力扣167题最优解就不再是哈希表而是双指针。初始化左指针left 0右指针right numsSize - 1。如果nums[left] nums[right] target直接返回如果和大于target说明右指针指向的数太大右指针左移如果和小于target说明左指针指向的数太小左指针右移。为什么这个算法不会漏解你可以这样理解数组有序那么nums[left] nums[right]决定了当前“搜索空间”的边界。当和太大时任何比右指针更靠右的元素都不可能让和变小所以右指针只能左移反之亦然。每一步都排除一整行或一整列时间复杂度O(n)空间复杂度O(1)比哈希表更省。从这道题到167题核心变化是“利用有序性”。面试时如果拿到的是有序数组而你还在写哈希表大概率会被追问一句“有没有更省空间的做法”。所以刷题时一定得把这两题放在一起看。5.2 不允许额外空间排序加二分还有一种变体要求不开额外空间但数组是乱序的哈希表不能用这时只能先排序再对每个元素二分查找target - nums[i]。排序成本是O(n log n)查找成本是O(n log n)。这个方案的代价是排序会改变元素顺序如果你需要返回原数组的下标就必须额外保存原始下标或者用结构体把值和下标绑在一起再排序。很多人在这一步卡住是因为排序后下标丢了。实际工程里我们经常用“索引数组”或“结构体数组”解决这类问题这也算一个很通用的建模技巧。5.3 从两数之和到三数之和思维升级的套路有了两数之和的基础三数之和就顺理成章了先排序固定第一个数剩下的两个数用双指针去找并注意跳过重复元素。四数之和再多套一层循环。你会发现两数之和里的“先查再插”思想到了三数之和里变成了“排序加双指针”哈希表反而不是最优解了因为去重逻辑会很麻烦。力扣热题100里围绕这个思路串起来的好几道题都值得做167两数之和II、15三数之和、18四数之和甚至还有“最接近的三数之和”。刷完这一串你会发现两数之和教的不是那个函数怎么写而是一整套“如何从暴力到优化”的思维路径。我在实际刷题中的感受是第一题的价值不在于“AC”而在于它逼着你把C语言的内存管理、返回值约定、手写数据结构这些基本功过了一遍。你把这套东西彻底搞明白后面再刷数组、链表、哈希表相关的题目都会顺畅很多。至少当你在力扣热题100里刷到中后段回头看到这道被标记为“简单”的第一题时你会真心觉得它其实是C语言新手的一座分水岭。