C语言两数之和源码拆解：指针、内存与哈希表实战

简介：这份资源是 LeetCode 经典入门题「两数之和」的 C 语言实现源码，面向正在刷题备战算法面试的初学者与在校学生，帮助理解如何在给定整数数组中查找和为目标值的两个元素，并返回其下标。题目假设每个输入只对应一种答案，且同一元素不可重复使用，示例中 nums=[2,7,11,15]、target=9 时返回 [0,1]。压缩包共 35 个文件，约 1.05MB，除核心 cpp 源码外，还包含 sln 解决方案、vcxproj 工程配置、rc 资源脚本、filters 筛选器以及 pdb、obj、ilk、ipch 等编译调试中间产物，另有 manifest、tlog、log 等构建日志，完整保留了 Visual Studio 工程结构，便于直接打开编译运行。目前已有 5676 人学习下载，读者可借此掌握暴力枚举与哈希表两种解法的代码组织方式，并参考工程配置与调试文件排查编译问题，适合作为算法入门与 C 语言工程实践的第一手参考。

1. 从一道题看透 C 语言的内存与指针：这份两数之和源码到底值不值得拆

很多人刷 LeetCode 的第一题就是「两数之和」，用 Python 或 Java 写出来可能不到十行，提交通过就翻篇了。但如果你正在学 C 语言，或者准备用 C 去应付嵌入式、系统编程方向的面试，这道题的价值远不止「做出来」——它逼着你直面数组指针退化、malloc 返回值检查、哈希表手写实现、返回数组长度怎么传这些 C 语言里绕不开的硬骨头。我手上这份 LeetCode 两数之和 C 语言源码，不是那种只给一个暴力双重循环就完事的敷衍版本，它把暴力法、排序双指针法、手写哈希表法三条路线都拆开写了，每一条都能单独编译运行。适合谁？适合刚学完 C 语法、想通过一道题把指针和内存管理串起来的初学者，也适合工作几年但一直用高级语言、想回头补 C 底子的开发者。下面我按「先跑通、再拆解、后避坑」的顺序，把这份源码里里外外讲一遍。

2. 三种解法逐行拆：从 O(n²) 到 O(n) 的 C 实现路径

2.1 暴力双重循环：最笨但最不容易翻车的起点

拿到任何算法题，我习惯先用最直白的写法把逻辑跑通，再考虑优化。两数之和的暴力法就是两层循环，外层固定一个数，内层从它后面找另一个数，看加起来是否等于目标值。这份源码里暴力法的函数签名是这样的：

// 暴力法：返回两个下标组成的数组，通过 returnSize 传出长度 int* twoSumBruteForce(int* nums, int numsSize, int target, int* returnSize) { // 外层遍历每一个元素作为第一个加数 for (int i = 0; i < numsSize - 1; i++) { // 内层从 i+1 开始，避免重复使用同一个元素 for (int j = i + 1; j < numsSize; j++) { if (nums[i] + nums[j] == target) { // 分配两个 int 的空间存放结果下标 int* result = (int*)malloc(2 * sizeof(int)); if (result == NULL) { // 必须检查 malloc 是否失败 *returnSize = 0; return NULL; } result[0] = i; result[1] = j; *returnSize = 2; // 告诉调用方返回数组有几个元素 return result; } } } *returnSize = 0; // 没找到，长度置 0 return NULL; }

这段代码里有两个 C 语言新手最容易忽略的点。第一，returnSize是一个指向 int 的指针，函数内部通过*returnSize = 2把结果数组的长度「传出去」。C 语言函数只能有一个返回值，想同时返回数组指针和长度，就必须用这种指针参数的方式。第二，malloc之后一定要判空，虽然 LeetCode 环境里几乎不会失败，但养成习惯比什么都重要，真实项目里内存分配失败不处理就是崩溃。

参数说明：nums是输入数组，numsSize是数组长度，target是目标和，returnSize是输出参数。时间复杂度 O(n²)，空间复杂度 O(1)（不考虑返回结果占用的空间）。这个版本适合用来验证你对下标边界和指针传参的理解，但不适合作为最终提交，因为数据量一大就会超时。

2.2 排序加双指针：理解「下标丢失」这个经典陷阱

暴力法之后，自然的优化思路是排序。排好序的数组可以用左右两个指针向中间逼近：左指针指向最小值，右指针指向最大值，如果两数之和小于目标值，左指针右移；大于目标值，右指针左移；相等就找到了。这份源码里排序双指针法的核心逻辑如下：

// 用于 qsort 的比较函数，升序排列 int compare(const void* a, const void* b) { return (*(int*)a - *(int*)b); } // 排序双指针法：需要额外保存原始下标 int* twoSumSorted(int* nums, int numsSize, int target, int* returnSize) { // 创建一个结构体数组，同时保存值和原始下标 typedef struct { int val; int idx; } Node; Node* nodes = (Node*)malloc(numsSize * sizeof(Node)); if (nodes == NULL) { *returnSize = 0; return NULL; } for (int i = 0; i < numsSize; i++) { nodes[i].val = nums[i]; nodes[i].idx = i; // 关键：记住每个值原来的位置 } // 按值排序，但下标跟着一起走 qsort(nodes, numsSize, sizeof(Node), compareNode); int left = 0, right = numsSize - 1; while (left < right) { int sum = nodes[left].val + nodes[right].val; if (sum == target) { int* result = (int*)malloc(2 * sizeof(int)); if (result == NULL) { free(nodes); *returnSize = 0; return NULL; } result[0] = nodes[left].idx; // 返回的是原始下标，不是排序后的 result[1] = nodes[right].idx; *returnSize = 2; free(nodes); // 临时数组用完必须释放 return result; } else if (sum < target) { left++; } else { right--; } } free(nodes); *returnSize = 0; return NULL; }

这里最大的坑就是「下标丢失」。如果你直接对原数组排序，排完之后元素的位置全变了，题目要求返回的是原始下标，你就对不上了。所以常见做法是额外建一个结构体数组，把值和原始下标绑在一起排序。这个思路在很多需要「排序但保留原始位置」的场景里都能复用，比如区间调度、成绩排名。

参数说明：compareNode是按val字段比较的函数，nodes是临时结构体数组，用完必须free，否则每次调用都泄漏一块内存。时间复杂度 O(n log n)，空间复杂度 O(n)。这个版本比暴力法快，但代码量翻了一倍，适合用来练习结构体和qsort的配合使用。

2.3 手写哈希表：C 语言里没有字典，只能自己造

高级语言里一行dict[nums[i]] = i就搞定的事，在 C 里得从头写哈希表。这份源码用的是开放寻址法里的线性探测，核心思路是：开一个固定大小的数组，每个位置存 key（数值）和 value（下标），插入时用哈希函数算出位置，如果被占了就往后找下一个空位。查找时同样先算哈希位置，然后逐个比对 key，直到找到或者遇到空位。

#define HASH_SIZE 2048 // 哈希表大小，取 2 的幂方便位运算取模 typedef struct { int key; // 存储数值 int value; // 存储原始下标 int used; // 标记该位置是否被占用 } HashEntry; // 简单的哈希函数：把整数映射到 [0, HASH_SIZE) int hash(int key) { return (key & 0x7fffffff) % HASH_SIZE; // 去掉符号位再取模 } int* twoSumHash(int* nums, int numsSize, int target, int* returnSize) { HashEntry* table = (HashEntry*)calloc(HASH_SIZE, sizeof(HashEntry)); if (table == NULL) { *returnSize = 0; return NULL; } for (int i = 0; i < numsSize; i++) { int complement = target - nums[i]; // 需要找的另一个数 int pos = hash(complement); // 线性探测查找 complement 是否已经在表里 while (table[pos].used) { if (table[pos].key == complement) { int* result = (int*)malloc(2 * sizeof(int)); if (result == NULL) { free(table); *returnSize = 0; return NULL; } result[0] = table[pos].value; // 之前存进去的下标 result[1] = i; // 当前下标 *returnSize = 2; free(table); return result; } pos = (pos + 1) % HASH_SIZE; // 冲突了就往后挪 } // 没找到 complement，把当前数插入表中 pos = hash(nums[i]); while (table[pos].used) { pos = (pos + 1) % HASH_SIZE; } table[pos].key = nums[i]; table[pos].value = i; table[pos].used = 1; } free(table); *returnSize = 0; return NULL; }

这段代码是三种解法里最长的，但也是最接近工程实践的。calloc会把内存清零，所以used初始都是 0，省去了手动初始化的步骤。哈希函数里key & 0x7fffffff是为了处理负数，因为负数直接取模结果还是负数，会导致数组下标越界。线性探测在表快满的时候性能会急剧下降，所以HASH_SIZE要开得比numsSize大不少，这份源码里固定 2048，对于 LeetCode 的测试数据量是够用的。

参数说明：HASH_SIZE决定哈希表容量，太小冲突多，太大浪费内存；hash函数决定分布均匀程度；used标记位用来区分「空位」和「存了 key=0 的位置」。时间复杂度平均 O(n)，最坏 O(n²)（所有元素哈希到同一位置），空间复杂度 O(n)。

3. 编译、测试与内存检查：把源码跑起来才算数

3.1 用 gcc 编译并跑通三个测试用例

拿到源码第一步不是读，是编译。这份源码包含一个main.c和三个解法函数，我一般会写一个简单的测试驱动来验证。编译命令如下：

# -g 带调试信息，-Wall 打开所有警告，-fsanitize=address 开启内存检测 gcc -g -Wall -fsanitize=address -o two_sum main.c ./two_sum

-fsanitize=address是 gcc 自带的内存检测工具，能抓出内存泄漏、越界访问、重复释放这些问题。对于手写哈希表这种涉及大量malloc/free的代码，这个选项几乎是必开的。如果你用的是 macOS，把-fsanitize=address换成-fsanitize=address同样有效，clang 也支持。

测试用例建议至少覆盖三种情况：正常找到两个数、数组中存在重复元素、找不到结果返回空。比如nums = [2,7,11,15], target = 9应该返回[0,1]；nums = [3,3], target = 6应该返回[0,1]；nums = [1,2], target = 10应该返回空。跑完如果 AddressSanitizer 没有报错，说明内存管理基本过关。

3.2 用 valgrind 做二次确认

AddressSanitizer 已经很强了，但有些平台或编译环境不一定支持。这时候可以用 valgrind 做补充检查：

# 先不带 sanitizer 编译 gcc -g -o two_sum_plain main.c # 用 valgrind 跑，重点看 definitely lost 和 invalid read/write valgrind --leak-check=full --show-leak-kinds=all ./two_sum_plain

输出里如果出现definitely lost: 0 bytes，说明没有内存泄漏；如果出现Invalid read of size 4，说明有越界访问，通常是哈希表探测时没控制好边界。我见过不少人写线性探测时忘了取模，pos一直自增直接冲出数组，valgrind 一跑就现原形。

3.3 三种解法的性能对比与选型建议

把三种解法放在一起跑同一组数据，能直观看出差距。下面是我用 10000 个随机整数测出来的大致结果：

选型建议很直接：如果只是理解题意，暴力法足够；如果面试官追问优化，排序双指针是稳妥答案；如果想展示 C 语言功底，手写哈希表最能加分。但要注意，哈希表解法在面试白板上写容易出错，尤其是冲突处理和边界判断，建议先在本地跑通再上考场。

4. 避坑与排查：C 语言写算法题最容易翻车的五个地方

4.1 返回数组长度没传出去，调用方拿到野指针

现象：函数返回了正确的下标数组，但调用方打印时只输出一个值或者直接崩溃。原因：returnSize没有赋值，调用方不知道数组有几个元素，可能按错误长度去读。解决：每个返回分支都必须设置*returnSize，找到结果设为 2，没找到设为 0，返回 NULL 之前也要设。

4.2 malloc 之后不判空，小概率崩溃难复现

现象：本地跑一百次都没事，换台机器或者跑大数据量时偶尔崩溃。原因：malloc在内存紧张时可能返回 NULL，直接解引用就是段错误。解决：每次malloc/calloc之后立刻判空，失败时释放已分配的资源并返回 NULL。这个习惯在 LeetCode 上看似多余，但迁移到嵌入式环境就是保命操作。

4.3 哈希表负数取模，数组下标变成负数

现象：程序在包含负数的测试用例上崩溃，报heap-buffer-overflow。原因：C 语言里-5 % 2048结果是-5而不是正数，直接用作数组下标就越界了。解决：哈希函数里先取绝对值或者用位运算去掉符号位，比如(key & 0x7fffffff) % HASH_SIZE。注意abs(INT_MIN)会溢出，位运算更安全。

4.4 排序后返回原始下标，结果对不上

现象：排序双指针法返回的下标在原始数组里找不到对应的两个数。原因：直接对原数组排序，元素位置变了，返回的是排序后的位置。解决：用结构体把值和原始下标绑在一起排序，返回时取结构体里的idx字段。这个坑在「两数之和 II」「三数之和」里同样存在。

4.5 忘记 free 临时数组，内存泄漏累积

现象：单次调用没问题，循环调用几万次后内存占用持续上涨。原因：排序双指针法里的nodes数组、哈希表解法里的table数组，在返回前没有释放。解决：每个malloc都要有对应的free，包括出错返回的路径。用 valgrind 跑一遍就能定位所有泄漏点。

5. 进阶技巧：把两数之和改造成可复用的 C 模块

5.1 用函数指针统一三种解法的调用接口

三种解法函数签名完全一致，这给了一个很自然的扩展点：用函数指针数组把它们串起来，写一个统一的测试框架。这样加新解法时不用改测试代码，只需要往数组里加一项。

// 定义解法函数指针类型 typedef int* (*TwoSumFunc)(int*, int, int, int*); // 把三种解法放进数组，方便批量测试 TwoSumFunc solvers[] = { twoSumBruteForce, twoSumSorted, twoSumHash }; const char* names[] = { "暴力法", "排序双指针", "哈希表" }; // 统一测试入口 void runAllSolvers(int* nums, int numsSize, int target) { int count = sizeof(solvers) / sizeof(solvers[0]); for (int i = 0; i < count; i++) { int returnSize = 0; int* result = solvers[i](nums, numsSize, target, &returnSize); printf("[%s] ", names[i]); if (result != NULL && returnSize == 2) { printf("下标: %d, %d\n", result[0], result[1]); free(result); // 谁分配谁释放，调用方负责 } else { printf("未找到\n"); } } }

这个模式在真实项目里很常见：定义统一接口，不同实现注册进去，测试和切换成本都很低。函数指针在 C 里是实现多态的主要手段，嵌入式里的驱动层、协议栈经常这么写。

5.2 把哈希表抽成独立模块，复用到其他题目

两数之和的哈希表实现稍加改造就能复用到「存在重复元素」「字母异位词分组」等题目。我一般会把HashEntry、hash、insert、find抽到一个hash_table.h和hash_table.c里，主文件只调用接口。这样下次遇到需要哈希的题，直接拿过来改 key 和 value 的类型就行。

// hash_table.h 接口定义 #ifndef HASH_TABLE_H #define HASH_TABLE_H typedef struct HashTable HashTable; // 不暴露内部结构 HashTable* hashTableCreate(int size); void hashTablePut(HashTable* ht, int key, int value); int hashTableGet(HashTable* ht, int key, int* value); void hashTableFree(HashTable* ht); #endif

封装成不透明指针的好处是调用方不需要知道内部用的是线性探测还是链地址法，以后想换实现也不影响上层代码。这个习惯从刷题阶段就养成，工作后写 C 模块会顺手很多。

5.3 一个我踩过的坑：LeetCode 的 free 和本地不一样

最后说一个血泪经验。LeetCode 的 C 判题环境对内存管理比较宽松，你返回的数组它负责释放，你中间漏 free 临时数组它也不一定报错。但本地用 AddressSanitizer 跑，同样的代码就会报泄漏。我一开始以为是本地环境有问题，后来才想明白：LeetCode 只检查结果对不对，不检查你有没有泄漏。所以刷题时最好本地开 sanitizer 跑一遍，把每个malloc和free都对上，别让判题机的宽容掩盖了坏习惯。从那以后我每次写完涉及动态内存的 C 代码，都强制用-fsanitize=address编译跑一遍测试用例，确认没有泄漏和越界才提交。希望这份源码和拆解能帮到你，把两数之和这道题真正吃透。

本文还有配套的精品资源，点击获取