很久以前。
大家写 C。
写数组。
写 for。
也写双重 for。
那时候你遇到“找一对数凑成目标值”。
第一反应不是“数据结构”。
第一反应是。
“我把它们都试一遍。”
它也确实能跑。
直到有一天。
它在凌晨两点。
把你的 CPU 打到 100%。
你看着监控。
心里冒出一句话。
“这题不是很简单吗？”
题目到底在问什么
LeetCode 的题在这里： https://leetcode.cn/problems/two-sum/
给你一组整数 nums，再给你一个目标值 target。
你要找两个不同位置的数，让它们相加等于 target。
最后返回这两个数的下标。
下标这事很重要。 因为它会让你很多“看起来聪明”的办法，突然没那么顺手。
先用很多例子，把题意讲到你点头
先来一个最经典的。
nums = [2, 7, 11, 15]
target = 9
答案是 [0, 1]。
因为 nums[0] + nums[1] = 2 + 7 = 9。
这里最容易把人绕晕的，其实不是 2 和 7。
而是“下标”。
你可以把它想成。
数组格子的编号。
nums : 2 7 11 15
index: 0 1 2 3
你返回的是格子号。
不是数值。
再来一个。
nums = [3, 3]
target = 6
答案是 [0, 1]。
注意。
不是 [0, 0]。
因为题目说的是“两 个 不 同 位 置”。
同一个元素不能用两次。
再来一个带负数的。
nums = [-1, -2, -3, -4, -5]
target = -8
答案是 [2, 4]。
因为 nums[2] + nums[4] = -3 + -5 = -8。
负数不是什么特殊情况。
它只是让你更容易在心算里出错。
再来一个很多人会忽略的。
nums = [0, 4, 3, 0]
target = 0
答案是 [0, 3]。
两个 0 是两个位置。
这题允许。
只是你别把它写成“拿同一个格子凑两次”。
还有一种。
答案在后半段。
你如果写错了“先记后查”的顺序。
会很容易绕进去。
nums = [8, 2, 7, 1]
target = 3
答案是 [1, 3]。
还有一条。
LeetCode 这题默认“恰好有一个解”。
所以你可以放心 return。
但在真实项目里。
你很可能遇到“没解”。
那你就得像我上面代码那样。
找不到就返回空。
新手最常在这几句话上皱眉
第一句。
“返回下标”。
你脑子里想的是数。
但函数要你交的是位置。
第二句。
“两个不同位置”。
它专门堵住了 [3] target=6 这种自嗨式答案。
第三句。
“恰好一个解”。
它是在告诉你。
不用纠结“返回哪一对”。
你只要把那一对找出来就行。
当年的老办法：双重 for
当年没有那么多现成轮子。
没有 unordered_map，甚至有些项目连 STL 都不敢用。
那怎么写？ 就这么写。
#include <vector>
std::vector<int> twoSum_bruteforce(const std::vector<int>& nums, int target) {
for (int i = 0; i < (int)nums.size(); ++i) {
for (int j = i + 1; j < (int)nums.size(); ++j) {
if (nums[i] + nums[j] == target) return {i, j};
}
}
return {};
}
它的逻辑非常“C”。 我把每一对都试一遍，找到就返回。 没有任何花活。
时间复杂度。
大概是 O(n^2)。
因为你基本把所有两两组合都试了一遍。
空间复杂度。
接近 O(1)。
因为你没有额外开一个“跟 n 一起长”的结构。
你如果刚学算法。
这其实挺好。
因为它把题目的语义一字不差地翻译成了代码。
// 找任意 i != j
// 让 nums[i] + nums[j] == target
翻译。
这就是第一步。
再给你一个“小数据手推”，你就知道它在干嘛
假设。
nums = [4, 1, 9, 7]
target = 8
双重 for 会这样试。
i=0: (4+1) (4+9) (4+7)
i=1: (1+9) (1+7)
i=2: (9+7)
你看。
它不是在“找答案”。
它是在“把所有组合列出来”。
列到某一对刚好等于 8。
它就停。
这段代码为什么会把你 CPU 打满
因为组合数量涨得太快。
你每多一个元素。
要试的对数就多一截。
你可以用一个不那么数学的说法。
n = 100 的时候。
要试大概 5000 对。
n = 10000 的时候。
要试大概 5000 万对。
你会明显感觉到。
它不是线性变慢。
它是“平方级”变慢。
线上啪一下：它为什么会突然慢得离谱
我见过最像 Two Sum 的事故，不在刷题网站上。 在一个小项目里，一个接口给用户推荐两张“凑单免邮”的商品。
目标金额 target 是免邮门槛。
商品价格就是 nums。
一开始数据量很小，双重 for 跑得飞快。 后来运营做活动，商品列表从几百涨到几万，接口开始超时。
你会看到这种代码。
bool has_pair(const std::vector<int>& prices, int target) {
for (int i = 0; i < (int)prices.size(); ++i) {
for (int j = i + 1; j < (int)prices.size(); ++j) {
if (prices[i] + prices[j] == target) return true;
}
}
return false;
}
这段代码在小数据时很温柔。 但它有个坏习惯：数据一大，它会把“试一遍”变成“试到天亮”。
你可以粗暴地把它理解成：数据有 n 个，它要比对大概 n*n/2 对。
n = 10,000 的时候就是五千万级别，n = 100,000 的时候就到几十亿了。
这就不是“慢一点”。 这就是“系统开始冒烟”。
先把时间复杂度/空间复杂度说人话
你刚学数据结构的时候。
第一次看到 O(n^2)、O(n log n)。
很容易误会。
以为这是数学题。
其实它在说一件很工程的事。
数据量变大以后。
你的程序大概会“怎么变慢”。
这里的 n。
通常就是输入规模。
在这题里。
大多数时候你可以把 n 当成 nums.size()。
时间复杂度。
你可以先理解成。
“要做多少次关键操作”。
比如比较多少次。
算多少次加法。
空间复杂度。
你可以先理解成。
“除了输入数据以外，我还额外占了多少内存”。
注意。
一般不把输入 nums 本身算进去。
我们更关心额外开销。
还有一个新手最常问的问题。
为什么 n*n/2 叫 O(n^2)？
因为 Big-O 只关心“级别”。
/2 这种常数系数。
对增长趋势没影响。
你把 n 翻倍。
n^2 会接近翻四倍。
这才是我们真正想盯住的东西。
人是怎么从坑里爬出来的：别枚举，先想“查”
双重 for 的本质是“枚举”。 把所有组合都翻一遍。
但 Two Sum 这题，你其实更想做的是“查找”。
我拿到一个数 x，就想知道 target - x 在不在里面。
你可以把它理解成翻电话簿。 你不是把全城的人都挨个问一遍，而是直接查名字。
关键就在这里。
查找能不能快一点？
这句听起来像算法。
但它其实更像工程。
你在问的是。
“我能不能把‘试一遍’变成‘查一下’？”
方案一：排序 + 双指针（先把“凑成 target”这件事写快）
先不管“下标”。
只看“有没有两数相加等于 target”。
一个很直觉的办法是排序。
有序了以后。
你可以用两个指针从两头往中间夹。
#include <algorithm>
#include <vector>
bool has_pair_sorted(std::vector<int> nums, int target) {
std::sort(nums.begin(), nums.end());
int l = 0;
int r = (int)nums.size() - 1;
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == target) return true;
if (sum < target) ++l;
else --r;
}
return false;
}
时间复杂度。
一般写成 O(n log n)。
不是因为双指针有多花。
而是因为排序那一步最贵。
log n 你可以先这么理解。
每多一倍数据。
排序要多忙一层。
所以增长趋势介于 n 和 n^2 之间。
空间复杂度。
这个版本是 O(n)。
因为我把 nums 按值传进来。
函数一进来就会拷贝一份数组。
如果你能接受原地排序。
把参数改成引用。
那这份拷贝就可以省掉。
这段代码的感觉和双重 for 完全不一样。 它不是“试所有组合”，它是在利用排序带来的结构。
sum < target 的时候左指针右移，因为左边太小。
sum > target 的时候右指针左移，因为右边太大。
它像是在“带着方向”地找，而不是瞎撞。 但它还没解决 LeetCode 要求的东西：下标。
你一排序，原来的位置就没了。
双指针到底在“指”什么
你可以把它想成。
我左手捏着最小值。
右手捏着最大值。
我俩一加。
如果小了。
就说明左手太小。
左手往右挪一点。
如果大了。
就说明右手太大。
右手往左挪一点。
它每次都在丢掉一大片不可能的组合。
所以它快。
方案一的补丁：排序时把下标一起带上
你可以把每个数和它的下标绑在一起。
排序的是数。
但身上背着原下标。
#include <algorithm>
#include <utility>
#include <vector>
struct ByValue {
bool operator()(const std::pair<int,int>& x, const std::pair<int,int>& y) const {
return x.first < y.first;
}
};
std::vector<int> twoSum_sort_two_pointers(const std::vector<int>& nums, int target) {
std::vector<std::pair<int,int>> a;
a.reserve(nums.size());
for (int i = 0; i < (int)nums.size(); ++i) a.push_back(std::make_pair(nums[i], i));
std::sort(a.begin(), a.end(), ByValue());
int l = 0, r = (int)a.size() - 1;
while (l < r) {
int sum = a[l].first + a[r].first;
if (sum == target) return {a[l].second, a[r].second};
if (sum < target) ++l; else --r;
}
return {};
}
时间复杂度。
还是 O(n log n)。
因为你还是要排序一次。
空间复杂度。
是 O(n)。
因为你额外建了一个 pair 数组。
它的长度跟输入一起长。
这里出现了一个新东西：pair。
你可以把它当成一个二元组：first 是值，second 是下标。
排序的时候看 first。
返回的时候吐出 second。
它是个挺“工程味”的补丁。
能用。
也挺稳。
代价是。
你要排序一次。
你如果还没系统学过 C++。
可能会问。
为什么不是自己写一个 struct？
也可以。
pair 的意义只是。
标准库里帮你准备好了一个“两个字段的小盒子”。
你拿来装一下值和下标。
少写一点样板代码。
方案二：哈希表（这题真正想让你学会的那一步）
现在回到最初那个念头。
我拿到 x，我就想知道 target - x 在不在。
如果能做到“很快就知道”，你就不需要排序，也不需要双指针。 你只要扫一遍。
这就是哈希表（hash table）的用法。 直觉也很朴素：你把一些东西塞进“桶”里，以后要找它，就按规则直接定位到桶。
在 C++ 里，最常用的现成工具是 std::unordered_map。
名字很长，你可以先只记住：它就是一个“查字典”的容器。
Two Sum 的 key 是“数值”，value 是“下标”。 写法通常是这样。
你可以把它当成一个“电话簿”。
我知道号码（数值）。
我就能查到那个人住哪一格（下标）。
#include <unordered_map>
#include <vector>
std::vector<int> twoSum_hash(const std::vector<int>& nums, int target) {
std::unordered_map<int, int> pos;
for (int i = 0; i < (int)nums.size(); ++i) {
int need = target - nums[i];
if (pos.count(need)) return {pos[need], i};
pos[nums[i]] = i;
}
return {};
}
时间复杂度。
平均情况下可以看成 O(n)。
你扫一遍数组。
每个元素都做一次查找。
再做一次记录。
空间复杂度。
是 O(n)。
因为 pos 里最多会放进接近 n 个 key。
这里新手最容易皱眉的是。
为什么不是拍胸脯的 O(1)？
因为哈希表的“快”通常是平均意义上的。
极端情况下。
很多 key 发生冲突。
查一次可能会变慢。
于是整体也可能退化。
读起来像在聊天。
我扫到 nums[i]，算出我还差多少 need，然后去字典里查一下。
如果之前见过 need，那我就找到了答案。
如果没见过，我就把当前这个数记下来，让后面的人来查我。
这几行 unordered_map 到底在干嘛
如果你刚从 C 过来。
最容易卡在这两句。
pos.count(need)。
pos[need]。
先说 count。
对 unordered_map<int,int> 来说。
pos.count(key) 只会返回 0 或 1。
意思就是。
“这个 key 在不在”。
再说 pos[need]。
它会返回这个 key 对应的 value。
但它还有个小脾气。
如果 key 不存在。
它会顺手把 key 插进去。
然后给一个默认值（对 int 来说就是 0）。
所以我这里先 count。
确认存在了。
再用 pos[need] 去取。
如果你不喜欢“可能插入”的行为。
也可以用 find 写一个更老派、但更直白的版本。
#include <unordered_map>
#include <vector>
std::vector<int> twoSum_hash_find(const std::vector<int>& nums, int target) {
std::unordered_map<int, int> pos;
for (int i = 0; i < (int)nums.size(); ++i) {
int need = target - nums[i];
std::unordered_map<int, int>::iterator it = pos.find(need);
if (it != pos.end()) return {it->second, i};
pos[nums[i]] = i;
}
return {};
}
你看。
这版唯一的代价。
就是 iterator 那个类型有点长。
但它不会偷偷插入。
读起来也更像“查字典”。
再来一次“手推”，你就能把哈希表写顺
用回那个经典例子。
nums = [2, 7, 11, 15]
target = 9
我们一边扫。
一边记。
i=0 x=2 need=7 表里没有 7 -> 记下 2->0
i=1 x=7 need=2 表里有 2 -> 返回 0 和 1
你会发现。
哈希表这招的核心不是“玄学”。
核心是顺序。
我只把“过去见过的数”记下来。
让“未来遇到的数”来查我。
“为什么要先查再放？”
这个顺序不是装酷。
它是为了避免拿自己跟自己配对。
比如 target = 6，当前数也是 3。
你如果先把 3 放进去。
再查 need = 3。
你就会把同一个下标配成一对。
先查再放。
就保证“字典里只有过去”。
不会把现在塞进去冒充过去。
这玩意到底是怎么来的：从符号表到字典
哈希表不是刷题网站发明的。
它更早。
早在大家写编译器的时候。
就有一个很实际的问题。
变量名一大堆。
我怎么快速查到“这个名字对应哪个变量”？
这东西叫“符号表”。
你不用记名词。
你只要记住它的味道。
就是“查字典”。
后来各种语言都开始内置这种字典结构。
Python 叫 dict。
Java 叫 HashMap。
C++11 之后标准库给你的是 unordered_map。
名字不同。
但用法很像。
都是 key -> value。
横向看一眼：不同语言是怎么“处理哈希表的坑”的
哈希表的坑其实就一个。
很多不同的 key。
可能会挤到同一个桶里。
这叫“冲突”。
处理冲突的办法。
各家不太一样。
Python 的 dict 很有名。
它偏向用“开地址”（open addressing）的思路。
桶里挤了就往后探一探。
Java 的 HashMap 也很有名。
它偏向用“桶 + 链表/树”的思路。
链表太长了还会做优化。
C++ 的 unordered_map 也有桶。
但你别急着背实现细节。
你只需要知道。
它们都在做同一件事。
尽量让“查一下”接近 O(1)。
再说一句老江湖的提醒
哈希表通常很快。
但它会吃内存。
而且它的“很快”是平均意义上的。
你在极端情况下也可能变慢。
工程里用它。
你要记得这个代价。
常见皱眉点：重复元素怎么办
nums 里可能有重复的数，比如 [3, 3]。
这段写法是没问题的：第一个 3 会被记录。
第二个 3 来的时候，一查就能查到第一个的位置。
然后返回 {0, 1}。
还有一个更隐蔽的。
如果 nums 里重复元素很多。
你要不要保存“第一个位置”。
还是“最后一个位置”？
这题因为保证只有一个解。
所以你随便存一个都行。
但你一旦把这个套路搬到真实项目。
比如你要找“所有解”。
那就不够了。
你就得把 value 从一个下标。
升级成“下标列表”。
你真正学到的，不是 unordered_map
Two Sum 这题很“经典”。 经典不在于它多难，而在于它把一个很工程的选择掰开给你看。
同样是“找一对东西”，你可以用双重 for 硬试。 也可以先排序再夹，还可以直接建一张表来查。
它们不是谁更高级，它们是在不同约束下的取舍。 数据小你用双重 for 省心，数据大你就得用“结构”换速度。
排序是用 O(n log n) 的预处理换更少的比较。
哈希表是用空间换时间。
横向对比总结：你到底该用哪一个
我一般这么选。
如果你只是想把功能先跑起来。 数据也不大。 就用双重 for。
它不聪明。 但它最不容易写错。
如果你能接受排序会改变顺序。 或者你本来就要把数据排一遍。 那就排序 + 双指针。
它的气质更像“整理过的搜索”。 用一点点排序成本，换掉一大堆枚举。
如果你不想排序。 也不想改动原数组的顺序。 那就用哈希表。
它的味道就是。 用空间换时间。
如果你刚学算法。
建议你把这三条路都写一遍。
不是为了背答案。
是为了在脑子里种下一个问句。
我现在做的是枚举。
还是查找。
参考与延伸阅读（你想深挖的时候再看）
如果你对“哈希表为什么快”感兴趣，可以翻《算法导论》（CLRS）里关于散列表的那一章。
如果你对“编译器为什么需要符号表”好奇，可以翻《龙书》（Compilers: Principles, Techniques, and Tools）里符号表那部分。
如果你想看工程实现，各语言官方文档也很有意思：Python dict、Java HashMap、C++ std::unordered_map。
结尾留一个亮点
Two Sum 最像的东西，其实不是“算两数之和”。 而是“把一次搜索变成一次查表”。
你以为你在写算法。
其实你在练习一种工程直觉。
当你开始问。
“我现在是在枚举，还是在查找？”
你已经从题目里走出来了。