刷过 LeetCode 的朋友对 167 这道题应该都不陌生它经常出现在“双指针”专题的第一页也被很多面试官当成 C 语言基础功的试金石。题目本身描述很简洁——给你一个下标从 1 开始的整数数组数组已经按非递减顺序排好序让你找出两个数使它们的和等于给定的 target返回这两个数的下标。我第一次做这道题的时候其实挺不屑的觉得不就是个两数之和吗结果用暴力解法写完一提交一看数据范围直接傻眼——数组长度最多能到三万个O(n²) 虽然也能过但那个耗时和内存占用摆在那里实在谈不上体面。这道题考察的核心能力其实有两个一是你能不能敏锐捕捉到“有序”这个条件带来的优化空间二是你能不能把指针移动的逻辑用 C 语言写得干净利落。这篇文章我打算把这道题的完整思考链拆开讲清楚包括三种主流解法各自的思路、C 语言实现细节、LeetCode 平台对返回值的特殊要求以及我实际调试时踩过的几个坑。不管你是刚开始刷题的新手还是想把 C 语言基础打扎实的在校生这篇文章都值得你花十分钟读一遍照着敲一遍代码收获会比单纯背答案大得多。1. 题目拆解与思路选择1.1 题目到底在问什么先原原本本把题目要点理一遍。函数签名是int* twoSum(int* numbers, int numbersSize, int target, int* returnSize)注意几个容易被忽略的细节数组下标从 1 开始计数也就是说示例里返回的[1, 2]对应的是数组的第一个元素和第二个元素而不是 C 语言习惯里的[0, 1]。这个细节每次都会坑到一批人。数组是有序的原题说的是“非递减顺序”也就是可能存在重复元素这一点在后面写二分查找的时候要格外留意。每个输入只对应一个答案而且同一个元素不能用两次。返回的数组必须是动态分配的因为 LeetCode 平台的检查逻辑是拿你返回的指针去比对结果比对完成后由它自己调用free()释放。如果你返回一个栈上数组的指针平台在 free 的时候会直接崩给你看。这些约束单独看都不难但组合在一起就决定了 C 语言解法的很多实现细节。你写出来的代码不仅要算法正确还要符合平台的内存管理约定否则就算逻辑全对提交也会报错。1.2 为什么“有序”是关键信息很多初学者拿到题会下意识写两层for循环暴力枚举这当然能做对但完全浪费了题目给的最重要线索。你可以思考一个问题如果这不是一个有序数组你会怎么办大概率是用哈希表一遍遍历把target - numbers[i]存进哈希表再查后面的数有没有出现过。但 C 语言标准库没有内置哈希表你得自己手写一个开链哈希或者用开放寻址法代码量直接翻倍笔试和面试这种时间紧张的场景根本来不及。而数组一旦有序我们就有了一种不需要任何额外内存的解法——双指针。它利用的数学性质很朴素对于有序数组左边的数小、右边的数大。当左指针和右指针指向的数相加等于 target 时直接返回如果相加结果小于 target说明左边的数太小了左指针右移如果结果大于 target说明右边的数太大了右指针左移。每一步都排除了一个数时间复杂度只有 O(n)空间复杂度 O(1)。这种“利用单调性收缩区间”的思想在后面的许多题目里都会反复出现比如「盛最多水的容器」「三数之和」「最接近的三数之和」。所以这道题与其说是在考两数之和不如说是在给你建立一种条件反射看到有序就想双指针看到无序才考虑哈希表。1.3 三种解法对比与选型这道题常见的解法有三种我用一个表格把它们的核心差异列出来方便你根据场景选择解法时间复杂度空间复杂度核心思路适用场景暴力枚举O(n²)O(1)两层循环逐个尝试只在理解题意时用不推荐提交双指针O(n)O(1)左右指针向中间收缩数组有序时首选二分查找O(n log n)O(1)固定一个数二分找另一个面试让讲多种方法时的加分项双指针是这道题的最优解也是面试官最想听你讲出来的思路。但二分查找的思路也值得掌握一方面它能体现你对有序数组内在结构的理解另一方面这种“枚举一个数 二分找另一个数”的组合模式在很多实际问题里都能派上用场。下面我把这两种解法的 C 语言实现都贴出来逐行讲清楚。2. 双指针解法原理与 C 语言实现2.1 指针移动的内在逻辑先别急着看代码我把双指针为什么正确这件事讲透。假设数组是[2, 7, 11, 15]target 是 9。初始时左指针left 0指向 2右指针right 3指向 15两者之和是 17比 target 的 9 大。注意观察左指针左边没有元素右指针右边也没有元素当前区间就是整个数组。2 15 17 9这意味着什么意味着如果固定左边的 2 不动那么 15 右边不可能有更小的数来降低和因为 15 已经是最大的数了而且它右边也没有元素所以唯一的可能是右边太大了。那我们就把右指针左移一位指向 11。现在2 11 13还是大于 9同理右指针再左移指向 7。这时2 7 9正好命中返回下标[1, 2]。反过来如果和小于 target说明固定右指针时左边的数太小了左指针右移。这种每次移动一个指针、排除一个“绝对不可能”的元素的做法保证了我们不会漏掉任何一对正确答案。你可以把它类比成小时候玩过的猜数字游戏对方心里想一个 1 到 100 的数以“大了/小了”为反馈每次排除一半的可能。双指针每次排除的不是一半但也是一段连续区间所以总体线性收敛绝不会回头重复计算。2.2 完整代码逐行拆解直接贴代码使用注释标注关键位置#include stdlib.h int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) { // 先按题目要求分配返回数组 int* result (int*)malloc(2 * sizeof(int)); *returnSize 0; // 先置 0防止找不到答案时返回野指针误导调用方 int left 0; int right numbersSize - 1; while (left right) { int sum numbers[left] numbers[right]; if (sum target) { result[0] left 1; // 题目要求从 1 开始计数 result[1] right 1; *returnSize 2; // 找到了长度置为 2 return result; } else if (sum target) { left; // 和太小左指针右移尝试更大的数 } else { right--; // 和太大右指针左移尝试更小的数 } } // 题目保证有解但防御性写法仍然必要 free(result); return NULL; }逐段解释几个要点。第一malloc(2 * sizeof(int))申请两个整型空间这里用了sizeof(int)而不是硬编码8是为了代码可移植性。有些平台int占 2 字节有些占 4 字节直接写8会在某些环境下出错用sizeof是最稳妥的。第二while (left right)这个循环条件用的是严格小于不是小于等于。因为题目要求两个数不能是同一个元素left和right相等时指向的是同一个位置如果条件写成理论上可能出现重复使用一个元素的情况。虽然有序数组里不会有两个相同的数加起来恰好等于 target 还能通过除非 target 是那个数的两倍但题目说每个输入只有唯一解且不使用同一元素所以不至于触发错误答案但从逻辑严谨性上讲才是正确的写法。第三*returnSize 2;这行很多人会漏。LeetCode 的检查器需要知道返回数组的长度如果你忘了设置returnSize调用方就不知道你到底返回了几个元素结果校验必然失败。我见过不止一个同学在本地测试时一切正常一提交就报错最后发现就是returnSize没有赋值。2.3 边界情况分析与压测这道题虽然题目保证有解但你在本地测试时依然要养成手动构造边界情况的习惯。我常用的测试用例有以下几组numbers [1, 2, 3, 4, 5], target 9答案是[4, 5]检验右指针一路左移的路径。numbers [1, 2, 3, 4, 4, 9], target 8答案是[4, 5]检验重复元素场景。numbers [-3, -1, 1, 5], target 2答案是[2, 4]检验负数场景。numbers [0, 1, 2], target 0题目保证有解但可能在某些变体里返回[-1, -1]表示不存在这个根据题目要求灵活处理。实际压测时可以把numbersSize设成 1 试试此时left 0, right 0循环压根不会进去直接走到free(result); return NULL;不会出现越界访问。这也是防御性编程的意义所在——即使平台明确保证不会给你这种非法输入你也要保证极端情况下不崩溃。3. 二分查找解法与两种方法对比3.1 二分查找的切入点双指针是从两端往中间逼近二分查找的思路则是从左到右固定一个数然后在它右侧的区间内用二分搜索target - numbers[i]。这个思路依赖的仍然是有序性既然数组非递减那么对于固定的numbers[i]剩下要找的数一定在i 1到numbersSize - 1这个区间内而且这个区间也单调有序可以直接二分。为什么这个解法也值得一提因为它在某些变体问题里比双指针更灵活。比如如果题目改成“无序数组中找两数之和”你没法直接用双指针但可以先排序再对每个元素二分查找目标差值。掌握这种组合模式能在笔试时多一层思路储备尤其是碰到那种“先排序、再枚举、再二分”的综合题时你会发现所有基础模板你都有数。当然就本题而言双指针的 O(n) 和二分查找的 O(n log n) 之间差距明显面试时如果能给出双指针就尽量别用它当主答案。但如果你把两种解法都讲出来面试官对你的印象会明显不一样——这代表你真的理解有序数组的性质而不是背了一道题的答案。3.2 C 语言实现细节二分查找版本的核心代码如下#include stdlib.h int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) { int* result (int*)malloc(2 * sizeof(int)); *returnSize 0; for (int i 0; i numbersSize; i) { int complement target - numbers[i]; int left i 1; int right numbersSize - 1; while (left right) { int mid left (right - left) / 2; // 防止溢出 if (numbers[mid] complement) { result[0] i 1; result[1] mid 1; *returnSize 2; return result; } else if (numbers[mid] complement) { left mid 1; } else { right mid - 1; } } } free(result); return NULL; }这里有个 C 语言新手特别容易犯的错mid (left right) / 2。当left right超过int最大值时加法本身就会溢出导致 mid 变成一个负数数组就越界了。题目里numbersSize最大是三万left right最多六万根本不会溢出但面试时你要是写出mid left (right - left) / 2这种防溢出写法面试官会默认你是个有经验的人——因为这说明你见过真正大规模数据下的溢出坑而不是只在 LeetCode 的小数据里打转。这个细节几乎可以当成一个隐藏的加分项。另一个细节是外层循环for (int i 0; i numbersSize; i)其实没必要遍历到最后一个元素因为至少要留一个数给complement所以写成i numbersSize - 1更严谨。但为了方便理解遍历完整个数组也不会出错——当i是最后一个元素时left numbersSizeright numbersSize - 1内层循环条件left right不成立直接跳过。3.3 双指针和二分查找的选择依据把两种解法放在一起看它们对有序数组的利用方式其实不太一样双指针是一种“同时排除两端可能”的策略每一步移动都基于当前两个端点之和与 target 的大小关系属于贪心 单调性的结合。二分查找是“每次固定左端点在右侧子区间内定位精确值”本质上是一次次做折半搜索属于枚举 搜索的结合。从时间复杂度角度双指针明显更优从代码复杂度角度两种写法都属于“白板 5 分钟内能写完”的级别差别不大。如果你想要一个选择标准我的建议是面试优先双指针笔试练习两种都写一遍。双指针代表最优解二分查找代表你熟悉经典搜索范式两者都能讲清楚的人才是真正吃透了这道题。4. 边界条件、常见问题与调试实录4.1 容易踩的四个大坑我在指导别人刷这道题以及自己复盘时总结出 C 语言版本最常见的四个坑每一个都有可能让你明明思路正确却提交失败。第一个坑是返回下标没有加 1。这个最简单却最致命因为题目明确说了下标从 1 开始。很多人写着写着就回到了 C 语言的 0-based 习惯返回[0, 1]而不是[1, 2]本地测试时还拿numbers[0] numbers[1]去比对结果自然发现“代码没问题但提交不对”。排查方法也很简单在result[0] left 1这行打一个断点看赋值是否满足题目的计数规则。第二个坑是忘记 malloc。LeetCode 的 C 语言检查器不会接受你返回一个函数内定义的局部数组int result[2]因为函数返回后栈帧一销毁这个指针就变成野指针了。检查器对这个行为的处理方式一般是随机崩溃或者读取到被覆盖的值。记住一个铁律凡是返回数组的 LeetCode 题目C 语言解法的返回值要么来自 malloc要么来自全局变量绝不能是局部栈变量。第三个坑是没有设置*returnSize。这个前面提过但值得单独拿出来说因为它太隐蔽了。函数的四个参数里returnSize是一个输出参数调用方通过它知道返回数组的长度。如果你只 malloc 并返回指针却没写*returnSize 2检查器会认为返回数组的长度是 0 或者未定义结果校验直接失败。每次写完代码我建议对照参数列表逐个确认numbers是输入、numbersSize是输入、target是输入、returnSize是我必须写入的输出。第四个坑是忽略空指针检查。虽然题目保证输入有效但很多同学的本地测试框架可能会传NULL进来或者在找不到答案时直接使用了未初始化的result指针。防御性编程习惯应该贯穿始终先*returnSize 0退出时统一处理必要时free(result)再返回NULL确保调用方拿到的永远是明确的状态。4.2 一次真实的调试经历我印象最深的一次调试经历是这样的用双指针解法写完代码后本地测试用一个随机生成的 5 万元素数组压测结果在某个用例上进入了死循环。排查半天发现问题出在while (left right)里忘记更新指针——当时我在sum target分支里直接return了没问题但在sum target分支里我写的是left right - 1而不是left导致某些场景下左右指针反复横跳永远不相等。这是一个看起来很蠢但其实很容易犯的错误你脑子里想着“如果和太小那边界就一定在左侧中间位置”手一抖就写了个不对的表达式。从那以后我养成一个习惯任何需要指针或下标移动的循环先写出结束条件再确保每个分支都会更新前进变量避免出现“某个分支里变量不变循环永远跑不完”的经典死循环。4.3 常见问题速查表现象可能原因解决方法提交报错load of null pointer of type int返回数组没有 malloc或返回了局部数组使用malloc分配保证返回的指针仍有效结果校验失败但不报错*returnSize没有赋值或赋值不对确认*returnSize 2且在返回前设置结果下标差一位忘记下标从 1 开始返回值统一1本地测试超时或死循环指针移动分支写错检查每个分支是否都更新了 left/right大数据量下乱码或段错误数组越界 / 中间变量未初始化用left (right - left) / 2防溢出初始化结果指针5. 变体问题与思路扩展5.1 如果数组无序怎么办这道题还有一个常被追问的变体numbers不是有序的怎么求两数之和最常用的方法是哈希表遍历一次把target - numbers[i]当作键存入哈希表值存下标之后如果遇到一个数正好等于某个键说明找到了另一半。C 语言里没有现成的哈希表需要自己实现一个简易版本一般用固定大小的数组 链表解决冲突。不过如果是面试场景你可以直接说“用哈希表O(n) 时间、O(n) 空间”然后简要描述一下开链法的思路面试官一般不会让你在白板上完整写一个哈希表。如果是笔试场景那就老老实实写出来这也是 C 语言基本功的一部分。5.2 扩展到三数之和如果你已经吃透了双指针会惊讶地发现「三数之和」几乎就是一个现成的升级版先排序然后固定第一个数对剩余部分用双指针找两数之和等于目标值。这和本题的关系是直接的——有序数组 双指针这套组合在多个经典问题里反复出现。区别在于三数之和要去重需要处理重复元素跳过的问题。你能把 167 这道题的指针移动逻辑理解透再去写三数之和会感觉非常顺滑。5.3 题目变形的面试现场我也见过面试官把 167 改成“不仅找出答案还要返回所有可能的组合”。这时候双指针依然能打只是每次找到答案后不能立刻 return要记录当前组合然后同时左移和右移直到两个指针相遇。去重的方式是跳过重复值。整个过程的时间复杂度仍然是 O(n²) 级别虽然双指针部分对每一轮是 O(n)但外层要枚举固定数空间复杂度 O(1) 或 O(k) 取决于是否需要存储结果。充分掌握基础解法的好处就在这里不管题目怎么变底层逻辑你都了然于心剩下的只是缝合而已。总结收尾一些实操体会这道题在 LeetCode 上标的是 Easy但它的价值远不止“简单”两个字。我实际做题和带人的过程中发现能一遍写出双指针正确 C 语言版的人大概率具备两个习惯一是对题目给你的约束条件有敏感度知道“有序”是专门为了优化而存在的信号二是对平台的内存约定有敬畏心malloc 和 returnSize 这种细节烂熟于心。如果你刚写完这道题建议用二分查找解法再写一遍然后自己写几个边界测试用例跑一遍尤其是负数、重复元素、最小规模这三种情况。多写一遍不是浪费时间是在把“套路”变成“本能”。这种本能积累多了你面对陌生题目时才不会慌因为本质上所有新题都是从这几个老模板里演化出来的。