企业官网建设流程全解析

刷LeetCode四数之和这题时，很多人第一反应是排序加双指针，两分钟写完、提交、通过，然后关掉页面继续下一题。但如果你在面试里被追问一句"用C语言怎么通过哈希表实现四数之和"，还是会卡一下——因为C语言不像C++那样自带unordered_map，哈希表必须自己手写，去重逻辑还得自己一点点理清楚。这篇文章就专门讲这件事：如何用C语言手写哈希表，把四数之和完整解出来，并把所有去重细节、边界条件和踩坑过程原原本本过一遍。适合正在刷题、想补C语言数据结构的读者，也适合面试前突击哈希表应用场景的人。

1. 四数之和的题目本质：暴力枚举到哈希查找的思维路径

1.1 题目边界：返回全部不重复四元组，不是只判断存在性

四数之和的题面并不复杂：给定一个整数数组nums和一个目标值target，找出所有不重复的四元组[a, b, c, d]，使得四个数之和等于target。

关键点有两个：一是必须返回所有满足条件的组合，而不是只告诉你"存在或不存在"；二是组合不能重复，比如[1, 2, 3, 4]和[4, 3, 2, 1]属于同一个四元组，数组顺序不影响判定。

nums和target的范围都比较宽，LeetCode上nums[i]可以到正负10的9次方，target也是这个量级。这意味着C语言里直接用int做四数相加会溢出，必须用long long做中间计算。这个看起来很基础的问题，实际写代码时最容易翻车，后面我会专门说。

最暴力的做法是四层循环，枚举所有下标组合，时间复杂度是C(n, 4)。n=200时大概是6468万次组合，循环体再复杂一点，单测就会跑得很痛苦。而且暴力枚举还需要手动去重，先把四元组排序再比较是否相同，简直是把简单问题复杂化。

所以要想办法降低复杂度。核心思路其实很朴素：既然要找四个数，那就先固定前面两个数，剩下的问题退化成"在数组中找到两个数，它们的和等于某个固定值"——这就是经典的两数之和。

1.2 哈希表在四数之和里到底存什么：查"补数"而不是查"整个组合"

两数之和的标准解法里，哈希表的作用是"记账"：遍历数组时，把已经见过的值存进表里，对于当前值，只需要查一下"目标值减去当前值"是否出现过，存在就能配对。这里哈希表存的不是组合本身，而是"补数查找所需的中间信息"。

把这个思路平移到四数之和：排序后，先枚举第一层i和第二层j，固定住nums[i]和nums[j]，那么问题就变成了在j+1到n-1这个剩余区间里，找两个数使其和等于target - nums[i] - nums[j]。

这一步内部又是一个两数之和。用哈希表把"剩余区间中每个值出现了几次"记录下来，枚举第三个数的同时，直接查第四个数是否存在于剩余区间中。整个算法的时间复杂度是外层两层循环O(n²)，内部遍历和查表O(n)，合起来平均O(n³)。空间复杂度是O(n)，哈希表只存一层内部数据。

要注意的是：哈希表并没有让四数之和变成严格意义的O(n²)，它只优化了内层两数的查找效率，从"固定k后再遍历l的O(n)"降到"O(1)平均查询"。这是很多初学者最困惑的地方，以为标题里写了哈希表，就一定要整个算法都变成O(n²)，其实不然。

2. C语言哈希表选型：自己动手写一个链地址版本

2.1 结构体设计：为什么除了key还要一个count

C语言标准库里没有哈希表，工程上可以引入uthash这类第三方库，但刷题和面试场景下，手写一个够用的版本反而更能讲清楚原理，也能体现对指针、内存管理的掌握程度。

我平时最常用的手写哈希表是链地址法：一个固定大小的桶数组，每个桶上挂一个链表，哈希冲突的节点通过next指针串起来。

typedef struct HashNode { int key; int count; struct HashNode *next; } HashNode; typedef struct { HashNode *buckets[HASH_SIZE]; } HashTable;

这里有一个非常关键的设计点：count字段不是可有可无的装饰，它解决的是"重复值在数组里出现多次"的问题。

四数之和的场景里，第三个数的补数可能在剩余区间中出现多次。比如数组是[2, 2, 2, 2]，目标是8，固定前两个2之后，内部要找两个2的和等于4，这时候剩余区间里有两个2可用。如果哈希表只存"是否存在"，那么计数必须至少是2才能支持这种配对；如果只存一个简单的标志位bool，就完全没法区分"剩一个2"和"剩两个2"。

所以这里用计数方式存储，每次从表里取出一个当前元素时，就把对应计数减一，表里剩余的计数代表"在当前下标之后还有几个这样的元素可用"。

另外，桶数组大小选择素数，比如10007，能有效减少哈希值取模后的聚集现象。哈希函数我用的是比较常见的混合乘法散列。

2.2 哈希函数与负数key：C语言取模的一个隐蔽陷阱

哈希函数看起来简单，但在C语言里有一个非常容易踩的坑：负数取模。

很多初学者会写成return key % HASH_SIZE;，然后发现哈希表里出现负下标，程序直接崩溃。原因很简单，C语言中%运算符对负数取模的结果还是负数，比如-7 % 5在C里是-2，不是3。数组下标不能是负数，于是一访问buckets[-2]就完蛋。

常有人想用abs(key)来解决问题，这也会踩另一个坑：abs(INT_MIN)在标准C里是未定义行为，很多实现会返回一个负值，依然出错。四数之和的数组元素范围很大，完全可能遇到INT_MIN附近的数。

我的做法很直接：先把int强转成unsigned int，借助无符号整数的取模特性，把负数自动映射到合法下标范围。

static int hash_int(int key) { unsigned int k = (unsigned int)key; k = (k ^ (k >> 16)) * 0x45d9f3b; k = (k ^ (k >> 16)); return k % HASH_SIZE; }

这里乘法和异或只是做一层混淆，让相邻的key分布到不同桶里。需要注意的是，无符号整数乘法溢出是定义好的回绕行为，不会触发未定义行为，所以这段代码在标准C下是安全的。

3. 可复现的完整实现：排序 + 双循环 + 内部哈希

3.1 完整代码：从哈希表到主函数

下面给出完整可运行的实现。为了展示C语言手写哈希表的全部细节，我没有引入任何第三方库，全部基于标准库。

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #define HASH_SIZE 10007 typedef struct HashNode { int key; int count; struct HashNode *next; } HashNode; typedef struct { HashNode *buckets[HASH_SIZE]; } HashTable; static int hash_int(int key) { unsigned int k = (unsigned int)key; k = (k ^ (k >> 16)) * 0x45d9f3b; k = (k ^ (k >> 16)); return k % HASH_SIZE; } void ht_init(HashTable *ht) { memset(ht->buckets, 0, sizeof(ht->buckets)); } void ht_insert(HashTable *ht, int key) { int idx = hash_int(key); HashNode *p = ht->buckets[idx]; while (p) { if (p->key == key) { p->count++; return; } p = p->next; } HashNode *node = (HashNode *)malloc(sizeof(HashNode)); node->key = key; node->count = 1; node->next = ht->buckets[idx]; ht->buckets[idx] = node; } void ht_delete(HashTable *ht, int key) { int idx = hash_int(key); HashNode *p = ht->buckets[idx]; while (p) { if (p->key == key) { p->count--; return; } p = p->next; } } int ht_count(HashTable *ht, int key) { int idx = hash_int(key); HashNode *p = ht->buckets[idx]; while (p) { if (p->key == key) { return p->count; } p = p->next; } return 0; } void ht_destroy(HashTable *ht) { for (int i = 0; i < HASH_SIZE; i++) { HashNode *p = ht->buckets[i]; while (p) { HashNode *tmp = p->next; free(p); p = tmp; } ht->buckets[i] = NULL; } } typedef struct { int **data; int len; int cap; } Res; void res_init(Res *r) { r->data = NULL; r->len = 0; r->cap = 0; } void res_append(Res *r, int a, int b, int c, int d) { if (r->len == r->cap) { r->cap = r->cap ? r->cap * 2 : 16; r->data = (int **)realloc(r->data, r->cap * sizeof(int *)); } r->data[r->len] = (int *)malloc(4 * sizeof(int)); r->data[r->len][0] = a; r->data[r->len][1] = b; r->data[r->len][2] = c; r->data[r->len][3] = d; r->len++; } int cmp_int(const void *a, const void *b) { int x = *(int *)a; int y = *(int *)b; return (x > y) - (x < y); } int **fourSum(int *nums, int numsSize, int target, int *returnSize, int **returnColumnSizes) { if (numsSize < 4) { *returnSize = 0; *returnColumnSizes = (int *)malloc(sizeof(int)); return NULL; } qsort(nums, numsSize, sizeof(int), cmp_int); Res res; res_init(&res); HashTable ht; for (int i = 0; i < numsSize - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; if ((long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; if ((long long)nums[i] + nums[numsSize - 1] + nums[numsSize - 2] + nums[numsSize - 3] < target) continue; for (int j = i + 1; j < numsSize - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; if ((long long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break; if ((long long)nums[i] + nums[j] + nums[numsSize - 1] + nums[numsSize - 2] < target) continue; long long need = (long long)target - nums[i] - nums[j]; ht_init(&ht); for (int k = j + 1; k < numsSize; k++) { ht_insert(&ht, nums[k]); } for (int k = j + 1; k < numsSize; k++) { ht_delete(&ht, nums[k]); if (k > j + 1 && nums[k] == nums[k - 1]) continue; long long complement = need - nums[k]; if (complement < INT_MIN || complement > INT_MAX) continue; if (ht_count(&ht, (int)complement) > 0) { res_append(&res, nums[i], nums[j], nums[k], (int)complement); } } ht_destroy(&ht); } } *returnSize = res.len; *returnColumnSizes = (int *)malloc(res.len * sizeof(int)); for (int i = 0; i < res.len; i++) { (*returnColumnSizes)[i] = 4; } return res.data; }

这段代码在数据结构上偏教学目的，没有做内存池优化。如果你准备提交LeetCode，追求更极端的运行时间，可以把哈希节点的malloc改成预分配节点数组，那样能省掉几百万次堆分配。不过先把原理跑通，再谈优化。

3.2 关键步骤拆解：预统计、先删再查、结果收集

主流程分三个阶段。

第一个阶段是排序。排序带来两个好处：一是后续去重只需要比较相邻元素；二是剪枝条件可以直接用最大/最小的几个数做累加判断。

第二个阶段是外层双循环。i和j确定前两个数后，内层要做的是在j+1到n-1里找一对数，凑出need。注意这里不能直接在遍历k的同时往哈希表里动态插入，那是两数之和的经典做法，但放到四数之和的"枚举第三个数+去重"场景下会有一堆问题，我下一节单独讲。

第三个阶段是结果收集。我封装了一个Res结构来做动态扩容二维数组，res_append每次往结果表里追加一个四元组。returnColumnSizes是LeetCode接口要求返回每行长度，这里每行都是4。

3.3 为什么内部不能用两数之和的"先查后插"

标准两数之和的哈希表写法是：遍历数组时，先查当前值的补数在不在表里，再把当前值插入表里。这个写法简单优美，但搬到四数之和的内部区间时，会立刻出现两个问题。

第一个问题是自我匹配。假设need是2，当前nums[k]也是1，查补数时发现表里有1，而这个1其实就是当前元素自己。虽然可以额外限制"补数下标必须大于当前下标"，但在动态插入过程中，这个限制会变得很拧巴——因为你并不知道表里的那个1是之前插入的还是刚插入的，如果同一个值出现多次，你也没法准确判断剩余可用的数量。

第二个问题是重复组合不可控。比如全零数组[0,0,0,0,0]，内部区间全是0，使用"先查后插"会导致同一个四元组[0,0,0,0]被反复命中很多次，因为不同位置的0都能凑成配对。虽然可以通过输出时比较四元组来去重，但C语言里维护一个"已输出组合集合"不仅麻烦，而且容易出错。

所以我在代码里换了一种思路：先把j+1到n-1的整个区间全部插入哈希表，完成"预统计"；然后枚举k时，先把nums[k]从哈希表里删除一次，再查询补数。这个"先删再查"保证哈希表里的计数只代表当前位置之后剩余的可用元素，直接规避了自我匹配问题。配合第三个数k的去重条件，同一个四元组只会被输出一次。

这个设计是整个哈希表方案的核心，也是和网上很多简单示例区别最大的地方。

4. 去重逻辑拆解：三层循环各跳一次，第四个数天然不重复

4.1 i层和j层的跳重边界

四数之和的去重逻辑比两数之和复杂不少，因为要确保四个数的数值组合唯一，而不是下标唯一。

排序之后，第一层i的去重很简单：if (i > 0 && nums[i] == nums[i - 1]) continue;。意思是：如果当前值和上一个值相同，那么这个值作为第一个数的所有组合，已经在上一轮全部枚举过了，直接跳过。

第二层j的去重有一个常见的边界错误。很多人会写成if (j > 0 && nums[j] == nums[j - 1]) continue;，这其实是错的。因为j是从i + 1开始的，如果写成j > 0，当j == i + 1且nums[j] == nums[i]时，会被误判为重复而跳过，但实际上这是i固定后第一个合法的j，不能跳。

正确写法是if (j > i + 1 && nums[j] == nums[j - 1]) continue;。也就是只有j不是当前i后面的第一个元素时，才允许跳过重复值。

同理，第三层k的去重也要写成if (k > j + 1 && nums[k] == nums[k - 1]) continue;，而不是k > j。这里每一层的"第一个位置"都要特殊保护。

4.2 k层的跳重与哈希计数配合

第三层k的去重和前面两层有一点点区别：k的去重是放在ht_delete之后的。

在代码里，我先执行ht_delete(&ht, nums[k])，把当前下标的元素从哈希表里移除，再进行跳重判断，最后才查补数。这个顺序是有讲究的。

设想一下，如果先跳过重复的nums[k]，那么在跳过的这些位置上，它们作为"剩余元素"仍然是存在的，不能从哈希表里删除。比如数组[0, 0, 1]，k枚举到第二个0时，虽然因为重复而跳过查询，但这个位置的0对于后续的第三个位置来说，仍然是合法可用的补数来源。如果我先continue跳过而不删除，哈希表里就会多计一个0，导致后续查询补数0时误判为"存在于剩余区间"。

所以顺序必须是：先删除当前nums[k]，再决定是否跳过查询。这样即使跳过了查询，哈希表的计数也始终准确反映"当前下标之后"的元素分布。

4.3 用示例验证去重效果

我用LeetCode官方示例验证一下。排序后数组是[-2, -1, 0, 0, 1, 2]，target是0。

固定i=0，即nums[0]=-2。j=1，即nums[1]=-1时，need=3。内部预统计区间是[0, 0, 1, 2]。枚举k=4时，当前值是1，补数是2，哈希表里2的计数为1，于是得到[-2, -1, 1, 2]。

固定i=0，j=2，即nums[2]=0时，need=2。内部枚举k=3，当前值是0，补数是2，得到[-2, 0, 0, 2]。

固定i=1，即nums[1]=-1。j=2，即nums[2]=0时，need=1。内部枚举k=3，当前值是0，补数是1，得到[-1, 0, 0, 1]。

最终结果正好是三个四元组，没有重复也没有遗漏。

再看一个极端的全零数组[0,0,0,0,0]，target是0。排序后全是0。i=0，j=1时，need=0。内部预统计区间是[0,0,0]，计数3。枚举第一个k时，删除一个0，计数变2，补数是0，命中，输出一次[0,0,0,0]。后续k因为是重复值，全部跳过查询。i=1时，i>0 && nums[1]==nums[0]直接跳过。最终只输出一个四元组。这个例子能很好地检验去重逻辑是否健壮。

5. 翻车现场：两两配对O(n²)哈希方案的四个坑

5.1 空间爆炸：数对数量是O(n²)

很多人在看到"哈希表实现四数之和"时，第一反应是把所有两数之和提前算好，存到一个(和值 -> 数对列表)的多重哈希表里，然后再遍历一次所有两数之和去查补数。这样理论上内层查询是O(1)，总复杂度看起来是O(n²)，确实很诱人。

但第一个坑就是空间。所有数对的数量是C(n, 2)，也就是O(n²)。n=200时约2万个数对，内存还能接受；n=1000时约50万个数对，每个数对要存两个下标、两个对应的数值，再加上哈希节点结构体，内存轻轻松松几十甚至上百MB。这还没算上"同一个和值对应多个数对"带来的多条链表。

刷题环境通常有内存限制，而且哈希表节点是用malloc逐个分配的，50万个节点的申请和释放本身就慢得离谱。

5.2 下标互斥与数值去重混在一起

第二个坑是下标互斥。当你查到一个补数和当前数对匹配时，必须确认补数对应的那两个下标，和当前数对的两个下标完全不重叠。因为同一个位置不能同时出现在一个四元组里两次。

这个检查单独做并不难，麻烦的是它和数值去重混在一起。比如数组[1, 2, 3, 4, 5]，数对(0,1)的补数可能在数对(2,3)里，也可能在(2,4)里，这些都会形成不同的下标组合，但数值组合可能一模一样。你需要遍历补数对应的整个数对列表，逐个验证下标是否互斥、数值组合是否重复。

更麻烦的是，两个数对交换一下也能组成同一个四元组。(0,1)+(2,3)和(2,3)+(0,1)是同一个四元组，如果你在遍历时不做顺序约束，同一个结果会被输出两次。

5.3 方案适用性边界：只配回答"是否存在"

所以在实际工程中，两两配对的O(n²)哈希方案更适合做"存在性判断"：只要找到一个四元组就返回true，不需要列举全部结果。这种场景下，下标互斥和去重问题可以用"满足条件就立即返回"来规避，空间也还能接受。

但题目要求返回所有不重复四元组时，两个数对各管各的哈希表方案会迅速失控。C语言里没有现成的集合类型可以做结果去重，你要么自己写个哈希集合存四元组，要么对结果数组反复排序比较，实现难度陡增，而且很容易引入bug。

所以本文主体采用的方案是"排序 + 两层枚举 + 内部哈希两数查找"：哈希表仍然承担查找任务，但复杂度是O(n³)，而不是盲目追求O(n²)。说实话，这才是"哈希表实现四数之和"更务实的落点。

6. 双指针和哈希表版本的真实对比：什么场景选谁

6.1 复杂度与常数因子：双指针为什么总是更快

四数之和的双指针解法思路是：外层两层循环枚举前两个数，内层用left和right两个指针从两边往中间扫，每次根据当前四数和与target的大小关系移动指针。

表面上看，双指针和本文哈希表版本的时间复杂度都是O(n³)，但双指针的空间是O(1)（不算排序和结果存储），哈希表版本额外需要O(n)的哈希表空间。更重要的是常数因子差别巨大：双指针只用数组下标和几个变量，内存访问是顺序的，缓存友好；哈希表版本每个内部区间要重新初始化桶数组、malloc海量节点、沿链表逐个比较key，光内存分配和指针跳转就慢了一个量级。

我用LeetCode上n=200左右的测试数据实测对比过：双指针版本一般个位数毫秒跑完；哈希表版本因为每层内部都要重建哈希表，耗时通常是几十毫秒量级，内存占用也明显更高。如果n继续增大到1000以上，哈希表版本的内存分配开销会进一步放大。

6.2 哈希表版本的真正价值在哪

那是不是说哈希表版本就没用了？不是。

哈希表版本的价值体现在三个地方。第一是教学意义：手写哈希表能帮你把键值对设计、哈希函数、冲突处理、动态存储管理这些基本功串起来，这是双指针给不了的。

第二是应对变体题。有些题目会问"是否存在四个数之和等于target"、"找出一组下标"、"统计满足条件的组合数量"，或者target和数组非常大需要大量重复查询时，哈希表的"预统计"思路会变得有用。比如两两配对哈希方案在"只判断存在性"的场景下就是简洁高效的。

第三是面试中的表达能力。当面试官问"除了双指针，你还能怎么解"，你能快速讲出"内部两数用哈希表替代双指针"，说明你对哈希表的应用场景和复杂度权衡是真的理解，而不是只会背题。

所以我的建议很直接：刷题和面试默认先写双指针，稳、快、好实现；如果题目明确限制或者面试官追问哈希表方案，再上手手写哈希表版本。两个方案都会写的人，才算是真正把四数之和这道题吃透了。

最后说一个我实际调试时的技巧：写完哈希表版本后，我习惯再写一个四层循环的暴力版本，把两个函数的结果数组逐项比对。特别是在全零数组、重复值很多、target为负数等极端case上反复跑，能很快暴露去重逻辑里"边界写错"或"删除顺序搞反"的问题。我自己就曾在全零数组上翻过车，输出了一堆重复四元组，最后定位到原因不是哈希表本身，而是内部漏掉了"先删当前元素"这一步。像这种细节，光看代码不容易看出来，必须依赖暴力结果做交叉验证。