到O(n)的思维转换)
我第一次认认真真刷题翻开的第一道就是“两数之和”。那时候觉得简单两层 for 循环套上去半小时写出代码还挺得意。后来去面试面试官把这道题原封不动出给我我条件反射写了暴力解他追问了一句“能不能优化到 O(n)”我当场卡住。现在回头看这道题挂在“哈希表”这个标签下面真正要教会我们的不是某个 API 怎么调用而是一种思维转换把“在数组里找两个数”变成“在历史记录里查一个数”。这个转换一旦打通后面很多题都会顺手很多。这篇文章想把哈希表解两数之和这件事讲透从暴力优化到哈希表选型从代码顺序到边界测试再顺手把两数之和衍生的各类变体一起理一遍。无论你是刚接触算法的萌新还是准备面试想补细节的开发者这篇文章都可以当作一份比较完整的复盘笔记来看。1. 题目的真面目两数之和其实是一道查找题1.1 暴力解法为什么慢每次判断都在重头扫数组题目描述很简单给定一个整数数组nums和一个目标值target在数组中找出和为目标值的两个整数返回它们的下标。很多人第一反应是暴力枚举for (int i 0; i nums.size(); i) { for (int j i 1; j nums.size(); j) { if (nums[i] nums[j] target) { return {i, j}; } } } return {};这段代码没有任何逻辑错误但它的时间复杂度是 O(n²)。为什么慢慢在内层循环每次都在重新扫描整个数组。当外层指针走到第 i 个元素时内层要从 i1 开始再扫一遍。前面已经遍历过的那些元素没有被记下来下一次判断时又得重新问一遍“你和我配不配”。这就像一个丢三落四的人每次要找一封信都从整个抽屉开始翻明明上一秒刚看过那封信下一秒又忘了它放在哪。暴力解不是“错”而是“笨”。它没有利用已经扫描过的信息每次都在做重复劳动。1.2 转折点把“找两个数”换成“查一个补数”题目给了我们一个非常重要的等式nums[i] nums[j] target移项之后就是nums[j] target - nums[i]这个移项看起来平淡无奇却是整道题的核心转折点。原本我们思考的是“哪两个数相加等于 target”这是一种组合式思维需要两两配对。移项之后问题变成了当我站在 nums[i] 面前时我只想知道一个问题——target - nums[i] 这个“补数”之前在数组里出现过吗“之前出现过吗”本质上是一个查找问题。数组本身是无序的线性查找需要 O(n)于是整个算法又退化到 O(n²)。但如果我们在遍历过程中把已经看过的每个元素都放进一个查找速度很快的结构里那么每次判断补数是否出现过就只需要 O(1) 的平均时间。这个结构就是哈希表。1.3 空间换时间的代价与适用条件用哈希表解两数之和本质上是典型的空间换时间。时间复杂度从 O(n²) 降到 O(n)空间复杂度从 O(1) 涨到 O(n)。我们用了一个“额外抽屉”来装已经见过的数换来的是每次查询的高效率。那是不是所有题目都适合这么换不一定。空间换时间成立的前提是查询操作足够频繁且哈希表带来的收益能覆盖额外空间的成本。两数之和显然满足因为内层循环原本要做 O(n) 次的线性查询换哈希表后每次查询降到平均 O(1)收益非常明显。如果问题规模很小比如数组只有三五个元素暴力解反而更简单直接没必要动用哈希表。这个判断标准在后文讲变体时还会反复出现。2. 哈希表选型为什么必须是“值到下标的字典”2.1 题目要求返回下标所以 set 不够用确定用哈希表之后第二个问题是具体用哪种结构很多初学者第一次接触这道题时会想到set因为set能快速判断一个元素是否存在。但两数之和的要求是返回下标而不是“是否存在”。unordered_set只能告诉你“在不在”没有办法告诉你“在哪个位置”。所以这里需要的是一个“字典”结构把数组元素的值映射到它的下标键key数组元素的值 值value该元素在数组中的下标在 C 里对应unordered_mapint, int在 Python 里对应dict在 Java 里对应HashMapInteger, Integer。这个映射关系要记清楚后面所有讲解都建立在“值到下标”这个语义上。2.2 unordered_map、map、Python dict 三者怎么选同样是“字典”底层实现可能完全不同选错了会直接影响复杂度。以 C 为例std::unordered_map哈希表实现查找、插入的平均时间复杂度 O(1)std::map红黑树实现查找、插入的时间复杂度 O(logn)两数之和要求整体 O(n)所以必须选unordered_map。如果用map外层循环 n 次每次查询 O(logn)总体变成 O(nlogn)虽然比暴力解好但没有把哈希表的优势用到位。Python 的dict在标准实现里就是哈希表直接用即可。结构底层实现查找复杂度是否适合本题unordered_map哈希表平均 O(1)适合map红黑树O(logn)不适合复杂度偏高unordered_set哈希表平均 O(1)不适合无法存下标Python dict哈希表平均 O(1)适合面试时如果被问到“为什么不用有序的 Map”原因就在这里我们只关心“存不存在”和“下标是多少”并不关心元素之间的相对顺序不需要引入有序性带来的 O(logn) 成本。2.3 别把哈希表当成万能钥匙还看数据特征哈希表很强大但它不是所有两数之和问题的唯一答案。如果题目额外说“输入数组是升序排列的”那更优解可能是双指针因为可以利用有序性把空间优化到 O(1)。如果题目要求“找出所有不重复的组合”哈希表在处理去重时就会变得非常繁琐很可能不如“排序 双指针”来得干净。这说明选什么数据结构取决于题目给了什么条件、限制了什么资源。哈希表只是若干可能性中的一种不是模板。3. 标准代码的每一步都在防什么实现细节拆解3.1 一份能直接跑的 C 和 Python 实现这是最经典的哈希表解法。先用 C 写一遍class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hash; for (int i 0; i nums.size(); i) { int complement target - nums[i]; if (hash.find(complement) ! hash.end()) { return {hash[complement], i}; } hash[nums[i]] i; } return {}; } };Python 版本逻辑完全一致class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: hash_map {} for i, num in enumerate(nums): complement target - num if complement in hash_map: return [hash_map[complement], i] hash_map[num] i return []代码看起来很短但每一行都有讲究。尤其要注意循环体里那条语句的顺序先查补数再把当前元素放进哈希表。这个顺序不是随手写的下面用一个反例说明为什么必须这样。3.2 先查再插的顺序一个反例讲清为什么考虑一个非常简单的例子nums [3, 2, 4] target 6正确答案有两个候选3 3不成立因为 3 只出现了一次真正成立的是2 4下标是[1, 2]。如果代码写成“先插入、再查询”会发生什么i 0先把nums[0] 3插入哈希表然后查补数target - 3 3哈希表里已经有刚插入的 3并且它的下标是 0于是返回[0, 0][0, 0]这个答案是错的下标 0 表示的 3 被当成两个不同元素用了但数组里这个 3 只有一个。反过来看标准写法“先查询、再插入”i 0查补数 3哈希表为空查不到插入 3i 1查补数 4查不到插入 2i 2查补数 2哈希表里有下标是 1返回[1, 2]答案正确。这个顺序问题的本质是当前元素还不应该成为自己的“另一半”。只有当它作为“历史元素”被后面的元素查询时它才配对。所以在把当前元素存入哈希表之前必须先检查补数是否已经在表里。3.3 判断“存在”要用接口别用值判断还有一个很隐蔽的坑判断补数是否存在时不要用“取出来的值是否等于 0”这种方式。C 里有人会这样写if (hash[complement] ! 0) { return {hash[complement], i}; }看起来好像没问题因为下标从 0 开始如果哈希表里没有这个键unordered_map的operator[]会返回 0。但实际上这会翻车。例子nums [2, 1, 4] target 6正确答案是[0, 2]因为2 4 6。走一遍错误写法i 0插入2hash[2] 0i 1插入1hash[1] 1i 2nums[2] 4补数是2hash[2]的值是 0if (hash[complement] ! 0)判断为 false于是漏掉了正确答案问题就出在下标 0 这个合法值被当成了“不存在”的标记。所以判断存在性C 用find()Python 用inJava 用containsKey()。永远不要用一个可能合法的业务值去兼任“哨兵值”。这个教训在更复杂的工程代码里同样适用。4. 复盘多年后我才总结出的边界细节4.1 重复元素与下标覆盖为什么本题可以“容忍”数组里可能出现重复元素例如nums [1, 2, 2, 3] target 4如果两个2分别在下标 1 和 2遍历到第二个2时hash[2]会被覆盖成 2。之后遍历到3时补数是 1哈希表里能找到下标 0 的 1于是返回[0, 3]也就是1 3 4答案合法。但如果另一个合法答案2 2存在而1 3不存在呢比如nums [1, 2, 2, 2] target 4遍历到最后时hash[2]保存的是最后一个 2 的下标 3当前元素是 2补数是 2哈希表里有于是返回[2, 3]答案同样合法。为什么覆盖不会导致无解因为题目只要求返回任意一组答案。只要存在解遍历到后一个元素时它的补数一定已经在哈希表里所以至少能返回一组。这正是“返回任意一对”这个约束带来的宽松空间。如果题目改成“返回所有可能的组合”那这个哈希表实现就需要升级为“值到多个下标的映射”否则会漏解。理解题目约束比背代码重要得多。4.2 负数、零和空数组不要做任何隐含假设初学者写代码时经常默认数组元素都是正数或者 target 一定是正数。两数之和的题目里没有这个约束。看一个例子nums [-3, 4, 3] target 0正确解法是-3 3 0下标[0, 2]。哈希表处理负数没有任何额外成本complement target - num本身就能算出负数。真正需要注意的是不要自己脑补“元素范围大于等于 0”更不要在代码里写类似if (nums[i] target) continue;这种“优化”。这个剪枝在全是负数时完全失效甚至会把正确答案剪掉。空数组也需要考虑。nums为空时循环不会执行直接返回空结果。标准写法天然支持所以不需要为它写特判但面试时最好主动提一句“空数组直接返回空”显得有完备性意识。4.3 无解时返回什么代码完备性的分水岭题目保证有解所以返回空数组不会在在线评测里触发。但面试时面试官很可能会追问如果无解你的函数返回什么C 版本最后写了return {};Python 版本写了return []。这看起来简单却体现了一个函数是否具备完备性。这里还想分享一个我自己多年形成的习惯写完代码后在草稿纸上跑两个用例一个正常用例一个专门攻击自己的用例。比如[3, 2, 4]配target 6专门用来测试“会不会自己配自己”[2, 1, 4]配target 6专门用来测试“下标 0 是否被误判”。这两个用例能揪出绝大多数隐蔽 bug。5. 一个哈希表题长出的题型家族5.1 输入有序的两数之和用双指针省掉哈希表两数之和有一个常见变体输入数组已经按升序排列。这时有更省空间的解法——双指针。思路很简单两个指针分别指向数组两端计算当前和。如果和小于 target说明需要更大一点的数左指针右移如果和大于 target说明需要更小一点的数右指针左移。int left 0, right nums.size() - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) return {left, right}; if (sum target) left; else --right; } return {};为什么有序情况下双指针可行因为有序数组给了我们一个“单调性”左指针往右移和一定变大右指针往左移和一定变小。我们可以根据当前和的偏差安全地排除一部分搜索空间。这个解法的空间复杂度降到 O(1)比哈希表更优。对比两种思路无序用哈希表有序用双指针本质上是“根据数据特征选择最优策略”。5.2 三数之和为什么不首选哈希去重成本是主要矛盾三数之和可以看作两数之和的高维版固定一个数剩下的就是一个两数之和子问题。按这个思路哈希表似乎也能解但真正动手后会发现——去重太麻烦了。题目要求返回所有不重复的三元组不能有重复组合。用哈希表找两数时很容易找到同一组解多次需要在三个位置都做去重代码复杂度急剧上升。排序 双指针则能借助有序性在移动指针的同时自然跳过重复值实现简单得多。这个例子特别能说明一个观点哈希表不是万能的。它擅长“查找”却不擅长“去重”。遇到组合类题目先去想数据特征和去重要求再决定用哪套工具。5.3 设计一个支持重复数据的 TwoSum改存出现次数另一个高频 Follow-up 是设计一个类支持两种操作add(num)插入一个数find(target)判断当前集合中是否存在两个数的和等于 target这个变体和原题最大的区别在于数据不是一次性给定的而是动态加入的并且同一个数字可能出现多次。哈希表不能只存“值到下标”了而要存“值到出现次数”class TwoSum { private: unordered_mapint, int count; public: void add(int num) { count[num]; } bool find(int target) { for (auto [num, cnt] : count) { int need target - num; if (need num) { if (cnt 1) return true; } else if (count.count(need)) { return true; } } return false; } };关键逻辑在第 9 到第 13 行如果补数等于当前数本身只有当它的出现次数大于 1 时才算找到答案。这是原题“不能自己配自己”在设计版中的真正体现。这个问题经常作为两数之和的追加题出现考察的是对哈希表“键值语义”的灵活迁移原题存下标设计题存计数结构变了本质还是用哈希表加速查找。两数之和这道题我这些年重写过很多次。从第一次暴力解到后来熟背哈希模板再到研究各种变体最大的体会是它表面上是数据结构题实际上是“空间换时间”这一思维在查找问题上的经典示范。如果你正处在刷题初期建议把这题当成思维模板把“先查再插”的顺序、用接口判断存在性这两个细节刻进肌肉记忆。等到了面试面试官无论怎么追问你都能从原理上接住。最后再分享一个我自己的习惯每道题我都会在草稿纸上写两个用例一个正常通过一个专门攻击自己的代码。比如[3, 2, 4]配target 6。很多隐蔽的 bug都是这样在真正上考场之前被提前揪出来的。
我第一次认认真真刷题翻开的第一道就是“两数之和”。那时候觉得简单两层 for 循环套上去半小时写出代码还挺得意。后来去面试面试官把这道题原封不动出给我我条件反射写了暴力解他追问了一句“能不能优化到 O(n)”我当场卡住。现在回头看这道题挂在“哈希表”这个标签下面真正要教会我们的不是某个 API 怎么调用而是一种思维转换把“在数组里找两个数”变成“在历史记录里查一个数”。这个转换一旦打通后面很多题都会顺手很多。这篇文章想把哈希表解两数之和这件事讲透从暴力优化到哈希表选型从代码顺序到边界测试再顺手把两数之和衍生的各类变体一起理一遍。无论你是刚接触算法的萌新还是准备面试想补细节的开发者这篇文章都可以当作一份比较完整的复盘笔记来看。1. 题目的真面目两数之和其实是一道查找题1.1 暴力解法为什么慢每次判断都在重头扫数组题目描述很简单给定一个整数数组nums和一个目标值target在数组中找出和为目标值的两个整数返回它们的下标。很多人第一反应是暴力枚举for (int i 0; i nums.size(); i) { for (int j i 1; j nums.size(); j) { if (nums[i] nums[j] target) { return {i, j}; } } } return {};这段代码没有任何逻辑错误但它的时间复杂度是 O(n²)。为什么慢慢在内层循环每次都在重新扫描整个数组。当外层指针走到第 i 个元素时内层要从 i1 开始再扫一遍。前面已经遍历过的那些元素没有被记下来下一次判断时又得重新问一遍“你和我配不配”。这就像一个丢三落四的人每次要找一封信都从整个抽屉开始翻明明上一秒刚看过那封信下一秒又忘了它放在哪。暴力解不是“错”而是“笨”。它没有利用已经扫描过的信息每次都在做重复劳动。1.2 转折点把“找两个数”换成“查一个补数”题目给了我们一个非常重要的等式nums[i] nums[j] target移项之后就是nums[j] target - nums[i]这个移项看起来平淡无奇却是整道题的核心转折点。原本我们思考的是“哪两个数相加等于 target”这是一种组合式思维需要两两配对。移项之后问题变成了当我站在 nums[i] 面前时我只想知道一个问题——target - nums[i] 这个“补数”之前在数组里出现过吗“之前出现过吗”本质上是一个查找问题。数组本身是无序的线性查找需要 O(n)于是整个算法又退化到 O(n²)。但如果我们在遍历过程中把已经看过的每个元素都放进一个查找速度很快的结构里那么每次判断补数是否出现过就只需要 O(1) 的平均时间。这个结构就是哈希表。1.3 空间换时间的代价与适用条件用哈希表解两数之和本质上是典型的空间换时间。时间复杂度从 O(n²) 降到 O(n)空间复杂度从 O(1) 涨到 O(n)。我们用了一个“额外抽屉”来装已经见过的数换来的是每次查询的高效率。那是不是所有题目都适合这么换不一定。空间换时间成立的前提是查询操作足够频繁且哈希表带来的收益能覆盖额外空间的成本。两数之和显然满足因为内层循环原本要做 O(n) 次的线性查询换哈希表后每次查询降到平均 O(1)收益非常明显。如果问题规模很小比如数组只有三五个元素暴力解反而更简单直接没必要动用哈希表。这个判断标准在后文讲变体时还会反复出现。2. 哈希表选型为什么必须是“值到下标的字典”2.1 题目要求返回下标所以 set 不够用确定用哈希表之后第二个问题是具体用哪种结构很多初学者第一次接触这道题时会想到set因为set能快速判断一个元素是否存在。但两数之和的要求是返回下标而不是“是否存在”。unordered_set只能告诉你“在不在”没有办法告诉你“在哪个位置”。所以这里需要的是一个“字典”结构把数组元素的值映射到它的下标键key数组元素的值 值value该元素在数组中的下标在 C 里对应unordered_mapint, int在 Python 里对应dict在 Java 里对应HashMapInteger, Integer。这个映射关系要记清楚后面所有讲解都建立在“值到下标”这个语义上。2.2 unordered_map、map、Python dict 三者怎么选同样是“字典”底层实现可能完全不同选错了会直接影响复杂度。以 C 为例std::unordered_map哈希表实现查找、插入的平均时间复杂度 O(1)std::map红黑树实现查找、插入的时间复杂度 O(logn)两数之和要求整体 O(n)所以必须选unordered_map。如果用map外层循环 n 次每次查询 O(logn)总体变成 O(nlogn)虽然比暴力解好但没有把哈希表的优势用到位。Python 的dict在标准实现里就是哈希表直接用即可。结构底层实现查找复杂度是否适合本题unordered_map哈希表平均 O(1)适合map红黑树O(logn)不适合复杂度偏高unordered_set哈希表平均 O(1)不适合无法存下标Python dict哈希表平均 O(1)适合面试时如果被问到“为什么不用有序的 Map”原因就在这里我们只关心“存不存在”和“下标是多少”并不关心元素之间的相对顺序不需要引入有序性带来的 O(logn) 成本。2.3 别把哈希表当成万能钥匙还看数据特征哈希表很强大但它不是所有两数之和问题的唯一答案。如果题目额外说“输入数组是升序排列的”那更优解可能是双指针因为可以利用有序性把空间优化到 O(1)。如果题目要求“找出所有不重复的组合”哈希表在处理去重时就会变得非常繁琐很可能不如“排序 双指针”来得干净。这说明选什么数据结构取决于题目给了什么条件、限制了什么资源。哈希表只是若干可能性中的一种不是模板。3. 标准代码的每一步都在防什么实现细节拆解3.1 一份能直接跑的 C 和 Python 实现这是最经典的哈希表解法。先用 C 写一遍class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hash; for (int i 0; i nums.size(); i) { int complement target - nums[i]; if (hash.find(complement) ! hash.end()) { return {hash[complement], i}; } hash[nums[i]] i; } return {}; } };Python 版本逻辑完全一致class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: hash_map {} for i, num in enumerate(nums): complement target - num if complement in hash_map: return [hash_map[complement], i] hash_map[num] i return []代码看起来很短但每一行都有讲究。尤其要注意循环体里那条语句的顺序先查补数再把当前元素放进哈希表。这个顺序不是随手写的下面用一个反例说明为什么必须这样。3.2 先查再插的顺序一个反例讲清为什么考虑一个非常简单的例子nums [3, 2, 4] target 6正确答案有两个候选3 3不成立因为 3 只出现了一次真正成立的是2 4下标是[1, 2]。如果代码写成“先插入、再查询”会发生什么i 0先把nums[0] 3插入哈希表然后查补数target - 3 3哈希表里已经有刚插入的 3并且它的下标是 0于是返回[0, 0][0, 0]这个答案是错的下标 0 表示的 3 被当成两个不同元素用了但数组里这个 3 只有一个。反过来看标准写法“先查询、再插入”i 0查补数 3哈希表为空查不到插入 3i 1查补数 4查不到插入 2i 2查补数 2哈希表里有下标是 1返回[1, 2]答案正确。这个顺序问题的本质是当前元素还不应该成为自己的“另一半”。只有当它作为“历史元素”被后面的元素查询时它才配对。所以在把当前元素存入哈希表之前必须先检查补数是否已经在表里。3.3 判断“存在”要用接口别用值判断还有一个很隐蔽的坑判断补数是否存在时不要用“取出来的值是否等于 0”这种方式。C 里有人会这样写if (hash[complement] ! 0) { return {hash[complement], i}; }看起来好像没问题因为下标从 0 开始如果哈希表里没有这个键unordered_map的operator[]会返回 0。但实际上这会翻车。例子nums [2, 1, 4] target 6正确答案是[0, 2]因为2 4 6。走一遍错误写法i 0插入2hash[2] 0i 1插入1hash[1] 1i 2nums[2] 4补数是2hash[2]的值是 0if (hash[complement] ! 0)判断为 false于是漏掉了正确答案问题就出在下标 0 这个合法值被当成了“不存在”的标记。所以判断存在性C 用find()Python 用inJava 用containsKey()。永远不要用一个可能合法的业务值去兼任“哨兵值”。这个教训在更复杂的工程代码里同样适用。4. 复盘多年后我才总结出的边界细节4.1 重复元素与下标覆盖为什么本题可以“容忍”数组里可能出现重复元素例如nums [1, 2, 2, 3] target 4如果两个2分别在下标 1 和 2遍历到第二个2时hash[2]会被覆盖成 2。之后遍历到3时补数是 1哈希表里能找到下标 0 的 1于是返回[0, 3]也就是1 3 4答案合法。但如果另一个合法答案2 2存在而1 3不存在呢比如nums [1, 2, 2, 2] target 4遍历到最后时hash[2]保存的是最后一个 2 的下标 3当前元素是 2补数是 2哈希表里有于是返回[2, 3]答案同样合法。为什么覆盖不会导致无解因为题目只要求返回任意一组答案。只要存在解遍历到后一个元素时它的补数一定已经在哈希表里所以至少能返回一组。这正是“返回任意一对”这个约束带来的宽松空间。如果题目改成“返回所有可能的组合”那这个哈希表实现就需要升级为“值到多个下标的映射”否则会漏解。理解题目约束比背代码重要得多。4.2 负数、零和空数组不要做任何隐含假设初学者写代码时经常默认数组元素都是正数或者 target 一定是正数。两数之和的题目里没有这个约束。看一个例子nums [-3, 4, 3] target 0正确解法是-3 3 0下标[0, 2]。哈希表处理负数没有任何额外成本complement target - num本身就能算出负数。真正需要注意的是不要自己脑补“元素范围大于等于 0”更不要在代码里写类似if (nums[i] target) continue;这种“优化”。这个剪枝在全是负数时完全失效甚至会把正确答案剪掉。空数组也需要考虑。nums为空时循环不会执行直接返回空结果。标准写法天然支持所以不需要为它写特判但面试时最好主动提一句“空数组直接返回空”显得有完备性意识。4.3 无解时返回什么代码完备性的分水岭题目保证有解所以返回空数组不会在在线评测里触发。但面试时面试官很可能会追问如果无解你的函数返回什么C 版本最后写了return {};Python 版本写了return []。这看起来简单却体现了一个函数是否具备完备性。这里还想分享一个我自己多年形成的习惯写完代码后在草稿纸上跑两个用例一个正常用例一个专门攻击自己的用例。比如[3, 2, 4]配target 6专门用来测试“会不会自己配自己”[2, 1, 4]配target 6专门用来测试“下标 0 是否被误判”。这两个用例能揪出绝大多数隐蔽 bug。5. 一个哈希表题长出的题型家族5.1 输入有序的两数之和用双指针省掉哈希表两数之和有一个常见变体输入数组已经按升序排列。这时有更省空间的解法——双指针。思路很简单两个指针分别指向数组两端计算当前和。如果和小于 target说明需要更大一点的数左指针右移如果和大于 target说明需要更小一点的数右指针左移。int left 0, right nums.size() - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) return {left, right}; if (sum target) left; else --right; } return {};为什么有序情况下双指针可行因为有序数组给了我们一个“单调性”左指针往右移和一定变大右指针往左移和一定变小。我们可以根据当前和的偏差安全地排除一部分搜索空间。这个解法的空间复杂度降到 O(1)比哈希表更优。对比两种思路无序用哈希表有序用双指针本质上是“根据数据特征选择最优策略”。5.2 三数之和为什么不首选哈希去重成本是主要矛盾三数之和可以看作两数之和的高维版固定一个数剩下的就是一个两数之和子问题。按这个思路哈希表似乎也能解但真正动手后会发现——去重太麻烦了。题目要求返回所有不重复的三元组不能有重复组合。用哈希表找两数时很容易找到同一组解多次需要在三个位置都做去重代码复杂度急剧上升。排序 双指针则能借助有序性在移动指针的同时自然跳过重复值实现简单得多。这个例子特别能说明一个观点哈希表不是万能的。它擅长“查找”却不擅长“去重”。遇到组合类题目先去想数据特征和去重要求再决定用哪套工具。5.3 设计一个支持重复数据的 TwoSum改存出现次数另一个高频 Follow-up 是设计一个类支持两种操作add(num)插入一个数find(target)判断当前集合中是否存在两个数的和等于 target这个变体和原题最大的区别在于数据不是一次性给定的而是动态加入的并且同一个数字可能出现多次。哈希表不能只存“值到下标”了而要存“值到出现次数”class TwoSum { private: unordered_mapint, int count; public: void add(int num) { count[num]; } bool find(int target) { for (auto [num, cnt] : count) { int need target - num; if (need num) { if (cnt 1) return true; } else if (count.count(need)) { return true; } } return false; } };关键逻辑在第 9 到第 13 行如果补数等于当前数本身只有当它的出现次数大于 1 时才算找到答案。这是原题“不能自己配自己”在设计版中的真正体现。这个问题经常作为两数之和的追加题出现考察的是对哈希表“键值语义”的灵活迁移原题存下标设计题存计数结构变了本质还是用哈希表加速查找。两数之和这道题我这些年重写过很多次。从第一次暴力解到后来熟背哈希模板再到研究各种变体最大的体会是它表面上是数据结构题实际上是“空间换时间”这一思维在查找问题上的经典示范。如果你正处在刷题初期建议把这题当成思维模板把“先查再插”的顺序、用接口判断存在性这两个细节刻进肌肉记忆。等到了面试面试官无论怎么追问你都能从原理上接住。最后再分享一个我自己的习惯每道题我都会在草稿纸上写两个用例一个正常通过一个专门攻击自己的代码。比如[3, 2, 4]配target 6。很多隐蔽的 bug都是这样在真正上考场之前被提前揪出来的。
