第一次在面试里被问到 LeetCode 167 这道题是在一个外包驻场的二面。对方看了看我简历上的熟悉常用数据结构与算法直接从题库里抽了这题。我用 HashMap 三分钟写了个 O(n) 的解法自认为稳了结果面试官一句话把我问住了如果数组是有序的你能不能用 O(1) 的空间复杂度解决我当时愣了一下又写了个二分他才点头放过。那次之后我才意识到很多人眼里的LeetCode 167 两数之和 Java 题解其实不只是背个双指针模板那么简单它背后牵涉的是面试官对复杂度敏感度、边界处理和问题变种迁移能力的判断。这篇文章我准备从一个刷题老油条的角度把两数之和 IILeetCode 167这道题彻底拆开从三种主流解法的演进逻辑、双指针为什么是这道题的最优解、代码里每个边界的含义再到面试连环追问的应对思路最后附上从这道题延伸出去的一整个两数之和变种题全家桶。不管你是刚开始刷 LeetCode 的 Java 新人还是准备跳槽想巩固基本功的工程师这篇都值得花十分钟看完。1. 为什么一道简单题值得翻来覆去地做1.1 面试官在简单题里真正想看的东西大家刷 LeetCode 的时候很容易陷入一个误区简单题刷起来快、成就感低不如直接干困难题。但真实面试里尤其是 Java 后端岗位面试官在算法轮根本不会一上来就扔给你 hard 题他们更倾向于用一道 167 这种看起来人畜无害的 medium 偏 easy 的题目去测你三个方面。第一是 API 的熟悉度比如 HashMap 用没用熟、数组操作边界有没有下意识检查。第二是对复杂度的直觉大多数人第一反应是暴力能立刻优化到双指针或者哈希代表你有性能敏感的职业习惯。第三是沟通能力面试官会看你拿到题之后是闷头就写还是先分析有序这个条件再确认返回的下标是从 1 开始还是从 0 开始。LeetCode 167 这道题正好把三个考察点全部覆盖还埋了一个下标从 1 开始的经典陷阱所以它在各大公司的题库里出现频率极高被归入热门 100 题不是没道理的。1.2 这题和 LeetCode 1 的区别一个下标就坑掉一半人LeetCode 1 的经典题大家估计都背下来了给定无序数组返回两数之和等于 target 的下标从 0 开始。LeetCode 167 长得很像但有两个关键改动数组按升序排列返回值要求下标从 1 开始。恰恰是下标从 1 开始这个改动每年不知道坑掉多少人。我见过不少面试者在白板上双指针写得飞起最后 return 的时候写了个new int[]{left, right}面试官问你确定吗他还没有反应过来。按照题目要求numbers的下标是基于 1 的所以如果你找到了位置 left 和 right必须要返回left 1和right 1。这个细节在实际编码中非常容易变成 bug因为本地测试用例如果是基于 LeetCode 1 改的跑起来可能发现答案不对不是算法错了而是没有处理下标偏移。我在自己刷题的时候养成了一个习惯凡是题目里出现index starts from 1这类描述我一定会先在注释里写着return left 1, right 1提前给自己立 flag。2. 暴力、哈希、双指针三种解法各自的脾气2.1 暴力法能交差但只配当兜底暴力解法绝大多数人都能瞬间想到两层 for 循环i 从 0 到 n-1j 从 i1 到 n-1判断numbers[i] numbers[j] target就返回。代码确实简单五分钟写完时间复杂度 O(n^2)。但说实话这种解法在面试里顶多只能作为我想到的第一个解法说出来千万不要直接提交。为什么不推荐因为 LeetCode 167 的数组长度可以到 3 * 10^4O(n^2) 意味着最坏情况将近 9 亿次加法虽然 167 的测试用例未必能卡到这个量级但在真实面试中你写上暴力解法之后如果自己不提优化方向面试官大概率会觉得你只会写循环。暴力法唯一的应用场景是你刚接触算法、需要从最基础的两层循环理解问题解的结构。我在教别人刷题的时候会让他先写一遍暴力再让他去分析暴力为什么慢——用到的信息太少了每次比较完没有留下任何可复用的状态。这个分析过程比直接背双指针重要得多。2.2 哈希表空间换时间的首选但小朋友才做选择哈希表的思路在 LeetCode 1 里是人尽皆知的遍历数组每到一个数就检查target - numbers[i]是否存在于哈希表中如果存在就返回两个下标否则就把当前值放入哈希表。时间复杂度 O(n)空间复杂度 O(n)代码也是几分钟搞定。在 LeetCode 167 里哈希表同样可以 AC但说实话有点不讲武德了。因为题目给了升序排列这个核心条件却用哈希表的话这个条件就没有被利用上。面试官如果追问你能不能用 O(1) 空间哈希表解法就完全站不住脚。当然如果题目改成无序数组比如 LeetCode 1那哈希表才是最优解。所以我的建议是这道题你需要在脑子里同时装着哈希表和双指针两个方案。先跟面试官说哈希表复杂度 O(n)/O(n)紧接着说但是因为数组已经有序我们其实可以用双指针把空间复杂度降到 O(1)。这一套组合拳打下来比直接甩一个双指针给面试官更有说服力因为这展示了你对比不同方案的能力。2.3 双指针这道题最优雅的答案双指针为什么是这道题的最优解核心在于有序数组的单调性。我们设一个指针 left 指向数组开头right 指向数组结尾然后计算sum numbers[left] numbers[right]。此时有三种情况sum target直接返回。sum target说明当前两数之和太小了需要更大的数参与相加只能把 left 往右移动。sum target说明当前两数之和太大了需要更小的数参与相加只能把 right 往左移动。这个过程看起来像在夹逼答案每一步都根据当前和与 target 的大小关系排除掉一整行或一整列不可能的解。因为数组有序所以当sum target时如果保持 right 不动任何比 left 更左的数加上 numbers[right] 只会更小都不可能等于 target所以 left 右移是唯一合理的方向。同理sum target时只能让 right 左移。这个每步排除一批不可能解的思想就是双指针算法区别于暴力搜索的核心。它的时间复杂度是 O(n)因为 left 和 right 各自最多移动 n 次总共 O(n)空间复杂度 O(1)只用了两个指针变量没有任何额外数据结构。3. 双指针解法逐行精读从原理到边界3.1 为什么 left right 而不是 left right很多人写双指针的时候习惯性地把循环条件写成while (left right)。有没有想过为什么不是left right因为题目要求你必须使用唯一的一个元素也就是说numbers[i]不能同时被取两次。如果 left right那 sum 就是同一个数加两次不符合题意。即使numbers[left] * 2 target这个组合也是无效的。所以循环条件严格是left right当两个指针相遇时就说明已经把所有可能的 pair 都检查完了没有找到答案。这个道理其实和 LeetCode 1 里不能用同一个下标两次是一个逻辑。在面试里说清楚这一点会让面试官觉得你不是在背模板。另外还有一个隐含的好处是因为 left 和 right 一个从最小值开始、一个从最大值开始并且每次只移动一个指针所以双指针天然不会漏掉解。这个不重不漏的性质是可以用反证法证明的面试时如果被追问你可以简单说每次移动都排除了一个方向上所有不可能的组合最后要么找到要么两个指针相遇说明无解。3.2 移动指针的判据单调性就是你的指路灯移动指针的时候最容易出错的地方在于什么时候移动 left什么时候移动 right。有些同学会写 if-else 但是搞反方向或者没写 else 导致死循环。写之前默念一句话当前和小于 target说明需要更大的加数所以加小指针当前和大于 target说明需要更小的加数所以减大指针。我把这个逻辑做成了一张表方便你在脑子里固化当前状态含义对应操作sum target找到了returnsum target数太小了left寻找更大的加数sum target数太大了right--寻找更小的加数这个规则完全依赖数组的有序性。如果数组无序这个模型立刻失效因为你无法判断 left 右边和 right 左边的数到底谁大谁小。这也是为什么我在刷题时总会先看题目条件里有没有sorted这个词有的话先问自己能不能用双指针这已经成为肌肉记忆了。3.3 完整代码与常见写法变形直接给出 Java 的完整解法class Solution { public int[] twoSum(int[] numbers, int target) { int left 0; int right numbers.length - 1; while (left right) { int sum numbers[left] numbers[right]; if (sum target) { // 题目要求下标从 1 开始所以要加 1 return new int[]{left 1, right 1}; } else if (sum target) { left; } else { right--; } } // 根据题意一定会有一组解这里返回空数组是防御性写法 return new int[]{-1, -1}; } }这段代码有几点值得注意使用int[]字面量初始化返回而不是先new再赋值简洁且不容易出错。当 sum 小于 target 时只用left不要同时调整 right否则会跳过可能的答案。如果题目保证有解最后的return new int[]{-1, -1}其实永远不会执行但写上是好习惯防止编译器报missing return statement。另一种常见的写法变形是先求出int complement target - numbers[left]然后用二分查找在[left 1, right]区间里找 complement。这个解法的时间复杂度是 O(n log n)虽然不如双指针的 O(n)但在面试中提一嘴也能展现你思路的开阔。我把它放在第四章单独讲因为面试官偶尔会追问这个变体。4. 复杂度、对比和面试里的隐藏考点4.1 三种解法的复杂度对比表先把三种解法的复杂度放在一张表里方便直观对比解法时间复杂度空间复杂度是否利用有序性适用场景暴力双层循环O(n^2)O(1)否仅作为思路铺垫哈希表O(n)O(n)否无序数组找两数之和LeetCode 1双指针O(n)O(1)是有序数组找两数之和LeetCode 167二分查找O(n log n)O(1)是有序数组但想用更算法化的写法面试的时候我建议先分析暴力再说哈希最后说双指针。这样一层一层递进面试官能看到你思维的路径。如果你一上来就是双指针也不是不行但少了一些展示对比能力的机会。尤其是想面高级岗位的同学面试官很在意你是否知道为什么要在这些方案里选它。4.2 面试中的三种追问场景根据我自己的面试和被面经验关于 167 的追问大概有这么几类第一类追问你能把空间复杂度降到 O(1) 吗这是最常见的问题。回答的时候直接抛出双指针说明有序数组的单调性让夹逼可行。这类追问的潜台词就是哈希表的空间不符合我的要求。第二类追问如果数组无序双指针还成立吗这个问题要看你怎么回答正确的姿势是先说不成立或需要先排序但排序会破坏原始下标所以如果题目要求返回原始下标排序后需要额外记录下标映射。这里就能顺便提到 LeetCode 1 和 167 的适用边界。第三类追问如果元素有重复怎么办比如numbers [1, 1, 2, 3]target 4。双指针依然有效因为题目只要求返回任意一组解而重复元素不影响夹逼的正确性。但如果要返回所有不重复的 pair双指针需要加一个跳过重复值的逻辑。这一点放第五章展开讲。4.3 二分查找也可解O(n log n)的另类答案有些面试官会追问除了双指针你还能想到别的做法吗这时候抛出二分查找会显得你知识面比较完整。思路是固定一个较小下标的数numbers[i]然后在[i1, numbers.length-1]区间里二分查找target - numbers[i]。Java 里可以直接用Arrays.binarySearch但要留意它返回负数时的处理逻辑。参考实现import java.util.Arrays; class Solution { public int[] twoSum(int[] numbers, int target) { for (int i 0; i numbers.length; i) { int complement target - numbers[i]; int j binarySearch(numbers, i 1, numbers.length - 1, complement); if (j ! -1) { return new int[]{i 1, j 1}; } } return new int[]{-1, -1}; } private int binarySearch(int[] numbers, int low, int high, int target) { while (low high) { int mid low (high - low) / 2; if (numbers[mid] target) { return mid; } else if (numbers[mid] target) { low mid 1; } else { high mid - 1; } } return -1; } }每次二分是 O(log n)外层循环 n 次所以整体 O(n log n)。这个解法在面试里不用作为主答案但可以作为如果不用双指针还有哪些方法的补充体现思维的多样性。我不建议在正常的笔试环节用二分因为明明有 O(n) 的双指针没必要故意写一个更慢的解法。但如果你被问到如何优化能说出来就是加分项。5. 从 167 到两数之和全家桶变种题与扩展思路5.1 变种题矩阵一览刷题最忌讳的是孤立地刷一道题做完了就完事了。LeetCode 167 的变种在面试里出现频率极高我干脆整理了一张两数之和家族图谱方便你按图索骥题号/来源题目特征推荐解法和 167 的关系LeetCode 1无序数组返回下标HashMap167 的无序版本LeetCode 167有序数组下标从 1双指针本题LeetCode 15三数之和为 0排序 双指针167 的升级版LeetCode 16三数之和最接近 target排序 双指针同上加一个差值判断剑指 Offer 57递增数组找和为 s 的两个数双指针和 167 几乎一致LeetCode 653在二叉搜索树里找两数之和中序遍历转数组 双指针 / HashSetBST 场景下的两数之和这些变种题的核心思想都是排序 双指针或者哈希表但在具体场景里有一些微调。比如 LeetCode 15 三数之和你需要先用一个循环固定第一个数然后在剩余区间里用双指针找两数之和同时要跳过重复值否则结果会有重复三元组。把 167 的双指针吃透理解它单调性消除不可能解的思想再去做 15 会轻松很多。5.2 把双指针的思想迁移到三数之和举一个我经常在文章里提到的例子——LeetCode 15 三数之和。它的代码骨架是这样的class Solution { public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger res new ArrayList(); for (int i 0; i nums.length - 2; i) { if (i 0 nums[i] nums[i - 1]) { continue; // 跳过重复的第一个数 } int left i 1, right nums.length - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { res.add(Arrays.asList(nums[i], nums[left], nums[right])); // 跳过重复的 left 和 right while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--; } else if (sum 0) { left; } else { right--; } } } return res; } }你注意看内部的while (left right)其实就是 167 的双指针只不过外面多套了一层循环多了一个固定数nums[i]然后多了一些跳过重复值的逻辑。所以如果你 167 的双指针原理没吃透三数之和会写得很痛苦反过来如果 167 写明白了三数之和只是增加了一个维度。这就是为什么我一直强调不需要追求刷题数量而是要把每一道经典题的原理吃透然后把同一类思想串起来。两数之和是面试轮最基础、最常考、变种最多的题型用心弄懂 167 一条线能带出一大片。说到最后简单分享一点个人经验。我自己在刷 LeetCode 167 的时候曾经犯过一个低级错误在sum target的分支里没有注意题目要求下标从 1 开始结果连续三次提交失败最后一看错误信息才反应过来。从那以后我养成一个习惯每个题先读三遍题目把返回值规范、边界范围、是否有序这些关键条件用笔写在草稿纸上再动手写代码。这个习惯帮我避免了很多不必要的返工。另一个小技巧是如果你在面试中遇到这道题别急着写代码先跟面试官确认这个数组是不是已经升序、返回下标是从 0 开始还是从 1 开始、有没有唯一解这些确认过程既能让你的代码更稳也会给面试官留下这个候选人沟通习惯很好的印象。两数之和不难但能在简单题上表现出滴水不漏的工程素养才是面试真正想看到的。