LeetCode把这道双循环题考了200万次

一道被刷了200万次的入门题，藏着算法面试里最常见的认知陷阱。

Two Sum。LeetCode第1题，难度"简单"。但通过率常年卡在55%左右——意味着每两个提交的人里就有一个栽跟头。不是代码写不出来，是写完之后面试官问"还能优化吗"，当场愣住。

今天拆解这道题的两个变体：普通版Two Sum，和Sorted Two Sum。前者是哈希表的教科书案例，后者是双指针的经典场景。但90%的候选人上来就选了最慢的那条路。

暴力解法：每个人都写过的双重循环

原文作者的代码很诚实。外层循环固定一个数，内层循环往后扫，配对检查。找到就返回，找不到继续。

这段代码的正确率接近100%，但时间复杂度是O(n²)。数组长度1000时，最坏情况要跑50万次比较。面试官的表情会在你说出"暴力"两个字时微妙变化。

空间复杂度O(1)是唯一的安慰奖——没用额外内存。但在算法面试的评分体系里，这通常意味着"需要引导优化"。

作者后来提到Sorted Two Sum的暴力版本，几乎 identical（完全一致）：只是返回时把索引加了1。因为题目要求返回"位置"而非"下标"，从1开始计数。

这个细节坑过很多人。LeetCode的测试用例不会提醒你，提交报错后盯着输出看半天，才发现是索引偏移问题。

优化路径：为什么哈希表是标准答案

普通Two Sum的最优解是哈希表，时间复杂度降到O(n)。思路很反直觉：不是找"另一个数在哪"，而是问"我需要什么数"。

遍历数组时，把当前数存入哈希表。同时检查 target - 当前数 是否已存在。如果存在，直接返回两个索引。一趟扫描解决问题。

空间换时间。O(n)的空间复杂度，换来O(n)的时间复杂度。这是算法面试里最常见的 trade-off（权衡）模板。

Sorted Two Sum的情况更微妙。数组已排序，意味着可以用双指针：左指针从头，右指针从尾，和太大就右移，和太小就左移。O(n)时间，O(1)空间，比哈希表还省内存。

但很多人想不到。排序这个条件被白白浪费，继续用哈希表——能过，但不是最优解。面试官会记下来。

面试现场的隐藏考点

这道题的真正价值不在代码，在沟通。

候选人A：直接写哈希表，5分钟写完。面试官追问"如果数组已经排序呢"，愣一下，改双指针。

候选人B：先写暴力，主动分析复杂度，再讲优化思路，最后实现最优解。15分钟，但展示了完整的 problem-solving（问题解决）链条。

后者的评分通常更高。因为实际工作中，没人要求你第一时间写出完美代码，但需要你证明"我能迭代优化"。

原文作者的暴力解法，在面试语境下是"起点"而非"终点"。但很多人把它当成终点提交，然后收到拒信。

从一道题看LeetCode的训练逻辑

LeetCode把Two Sum放在第1题，不是因为它简单，是因为它够基础、够开放、够有延伸空间。

同一道题，可以考暴力、哈希表、双指针三种解法。可以追问空间限制下的优化，可以变形为Three Sum，可以改成"返回所有不重复组合"。

刷题时只追求"通过"，面试时会暴露思维深度。刷题时分析"有几种解法，各有什么优劣"，面试时才能从容应对 follow-up（追问）。

原文作者在Sorted Two Sum的结尾写了一句："This method works correctly but it takes more time." 这种自我觉察很重要，但停留在觉察层面不够。下一步应该是：我知道慢，那怎么变快？

算法面试的通过标准，从来不是"代码能跑"，是"在约束条件下找到合理方案，并能论证为什么合理"。

Two Sum的200万次提交里，有多少人在暴力解法后停下来想了一步？这个数据LeetCode不会公布，但面试官心里有数。

你现在刷这道题，会选哪条路起手——暴力、哈希表，还是先看数组排没排序？