企业官网建设流程全解析

第一次看到 “A-B 数对” 时，我脑子里冒出的解法是双重循环：对每个 A 再扫每个 B，看差值是不是 C。直到题面里 n 的上限写到 2e5，我才明白这道题真正想考的不是暴力，而是怎么把“差值为 C 的配对计数”从 O(n²) 压下来。

这里说的 map、set 和 lower_bound/upper_bound，是几个看起来很像、实际分工完全不同的工具。map 适合给每个值记出现次数；set 适合判断某个值是否存在；lower_bound/upper_bound 适合在有序区间里数出“等于某个值的一段有多少个”。A-B 数对刚好能把这三样东西的边界全部试一遍。我见过不少同学看到题解里“用 map”就照抄，遇到重复值之后一脸懵；也见过有人拿 set 做这题，结果统计次数时发现 set 根本不存次数。与其背结论，不如把这题背后的逻辑理清楚。

这篇文章适合正在学 C++ STL 的读者，也适合备赛时想搞懂“哈希计数 vs 排序二分”怎么选的人。我会从题面约束讲起，给出可以直接抄的代码，再把我实际踩过的几个坑一个个拆开。

1. 先看清 A-B 数对在问什么：别在题面理解上翻车

1.1 题意与两个关键约束

A-B 数对的问题描述通常长这样：给定一个长度为 n 的整数数组和一个整数 C，要求统计所有满足A - B = C的数对个数。这里的 A 和 B 都来自同一个数组，而且一般会强调“不同位置的数字一样的数对算不同的数对”。这句话不是废话，它直接决定了算法的写法。

举个例子，数组是[1, 1, 2, 2]，C = 1。那么满足条件的数对有多少？如果你只按数值看，A=2、B=1 这一种组合，好像答案就是 1。但按位置看，数组里有两个 1 和两个 2，每个 1 都可以和任意一个 2 组成数对，所以答案是 2 * 2 = 4。所有把“位置”算进去的计数题，本质上都在数“实例”，不是在数“数值种类”。

还有一个约束是数据范围。常见版本里 n 可以到 2e5，数组元素可以是 1e9 甚至更大的整数，C 也可能是 long long 级别的数。这个范围直接让很多“看起来正确”的写法失效。后面我会详细说。

1.2 朴素双重循环为什么必挂

最直觉的写法长这样：

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i] - a[j] == C) ans++; } }

这当然是对的，但 n = 2e5 时，循环次数是 4e10，在任何在线评测平台上都跑不过。哪怕 n 缩小到 1e4，双层循环也可能勉强卡过，但再来一组刁钻数据就原形毕露。所以核心矛盾不是“怎么判断相等”，而是“怎么把找配对的过程从遍历全部元素变成查一次表”。

看到A - B = C的式子，我建议第一反应不是直接套循环，而是做一步变形：A = B + C。也就是对于每一个 B，我们只需要知道数组里有多少个 A 等于B + C。这样一来，问题从“两两比较”变成了“查找一个固定值出现了多少次”。

1.3 固定 B 找 A，把配对问题变成查表问题

“固定 B，找 A”这个方向非常重要。如果你固定的是 A，那就要找A - C，本质一样，但 C 为正数时固定 B 更好理解，因为 A 在数值上偏大，B + C的语义很自然。

现在关键就变成：如何快速知道某个值在数组里出现了几次。这个问题有两条主流路线：

• 用 map 或 unordered_map 统计频次，查询时直接cnt[value]。
• 把数组排序，再用 lower_bound/upper_bound 找到等于 value 的区间长度。

这两条路线分别对应两种不同的思维模型。map 的模型是“我有一本账本，直接记每个值有几个”；排序二分的模型是“我有一串排好队的数，我数一下某个连续段里站了几个人”。两条路都能过题，但细节差别很大。

2. 第一版方案：用 map 给每个值记次数

2.1 为什么是 map 而不是普通数组

如果数组元素的范围很小，比如 0 到 1e6，那最粗暴的做法是开一个int cnt[1000005]，每个值出现一次就cnt[x]++。问题是当值域到 1e9，或者出现负数时，数组下标根本没法直接用。这时候 C++ 的 map 就派上用场了。

map 的本质是一个有序的键值对容器，底层通常是红黑树。每个不同的数组元素作为一个键，键对应的值就是它出现的次数。另一个选择是 unordered_map，底层是哈希表，查询平均 O(1)，但存在被构造数据卡成 O(n²) 的风险。两者在 A-B 数对里都能用，只是你要知道它们各自的脾气。

用 map 的另一个好处是：它天然处理负数。map<long long, long long> 的键可以是负数，这一点比数组下标方案友好太多。很多写着“C 是正整数”的题，数组元素也可能是负数，所以不要假设所有输入都非负。

2.2 map 计数 + 遍历的实现

这里我给出一个可以直接用的版本。为了速度更快，我用 unordered_map 做计数，但如果你比赛环境比较保守，换成普通的 map 也完全没问题。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long C; cin >> n >> C; vector<long long> a(n); unordered_map<long long, long long> cnt; for (int i = 0; i < n; i++) { cin >> a[i]; cnt[a[i]]++; } long long ans = 0; for (long long x : a) { ans += cnt[x + C]; } // 如果 C == 0，x + C == x，每个元素都把自己匹配了一次，需要扣掉 n if (C == 0) ans -= n; cout << ans << '\n'; return 0; }

这段代码的思路是：先把所有值出现的次数统计好，然后遍历原数组中的每一个元素，把它当作 B，去找B + C出现了多少次。累加结果就是答案。

稍微解释一下为什么C == 0要减去 n。当 C = 0 时，我们找的是x + 0 = x，所以每个元素都会把自己也算进cnt[x]里。如果是两个位置相同的元素，它不构成题目通常要求的“数对”，所以要把这 n 次自匹配扣掉。这个细节很多人第一次写都会漏，后面我会专门讲。

2.3 复杂度分析与 long long 的必要性

用 unordered_map 时，插入和查询平均都是 O(1)，总复杂度 O(n)。用普通 map 时，每次操作 O(log n)，总复杂度 O(n log n)。对于 n = 2e5 来说，两种都足够快。

但答案的数据类型一定要用 long long。最极端的情况是 C = 0 且所有元素都相等，那任意两个位置都能配成一对，答案大约是 n * (n - 1)，n = 2e5 时接近 4e10，int 一定会爆。另外x + C本身也可能超过 int 范围，所以数组和 C 最好都用 long long 存。

3. set 和 lower_bound/upper_bound 能做什么、不能做什么

3.1 set 只解决存在性，不解决频次

很多人会在 A-B 数对里想到 set，因为 set 的查找很快。思路大概是：把数组元素丢进 set，然后对于每个 B，检查B + C在不在 set 里。存在就说明有一对数。

这个思路在“所有元素都不重复”的简化版题目里确实能用，但放到本题就塌了。set 只能告诉你某个值存不存在，不能告诉你它出现了多少次。拿刚才的例子[1, 1, 2, 2]，C = 1，set 里只有{1, 2}，检查1 + 1 = 2存在，于是认为只有 1 对，实际却是 4 对。

所以我的建议是：看到“统计个数”先想 map 或排序数组，看到“判断是否存在”再想 set。set 在 A-B 数对里更适合当辅助工具，不适合当主力。

3.2 lower_bound/upper_bound 真正返回的是什么

lower_bound 和 upper_bound 是二分查找接口，但它们返回的不是“有没有找到”，而是“位置”。

• lower_bound(begin, end, x)返回第一个大于等于 x 的迭代器。
• upper_bound(begin, end, x)返回第一个大于 x 的迭代器。

如果两者之差不是 0，说明区间里存在等于 x 的元素，而且差值就是 x 在区间里出现的次数。拿数组[1, 2, 2, 3, 5]来说：

很多人总把 lower_bound 当成“找到这个值的位置”，其实它更像“这个值应该插入到哪里，才能保持有序”。理解了这一点，才能正确用它做区间计数。

3.3 用 multiset 数次数为什么反而慢

既然 set 去重不行，那用 multiset 行不行？multiset 允许重复元素，于是有人会写：

auto L = ms.lower_bound(x); auto R = ms.upper_bound(x); int cnt = distance(L, R);

问题在于 multiset 的迭代器不是随机访问迭代器，distance(L, R)只能通过一步步走的方式计算，复杂度等于区间长度。也就是说，查一次答案最坏要遍历一遍所有相同元素，整体复杂度又退化成了 O(n²)。看起来用到了二分，实际并没有省掉遍历。

真正能高效使用 lower_bound/upper_bound 的前提是有序的随机访问容器，也就是排序后的 vector 或数组。set 和 multiset 在“计数”场景下都不够理想，这也是为什么更稳的做法是把数组拉出来排序。

4. 更稳的做法：排序数组 + lower_bound/upper_bound 数区间

4.1 排序后，计数问题变成区间长度

既然无序状态不好统计，那就先排序。排序后所有相同的值会聚在一起，而一堆连续相同的值恰好形成一个区间。用 lower_bound 找到这个区间的左端点，用 upper_bound 找到右端点，右端点减左端点就是出现次数。

这个思路的核心在于：我们不再“查是否存在”，而是“数区间长度”。对于每一个 B，目标 A 是B + C，只要统计B + C在数组里出现了多少次就行。

代码长这样：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long C; cin >> n >> C; vector<long long> a(n); for (int i = 0; i < n; i++) cin >> a[i]; sort(a.begin(), a.end()); long long ans = 0; for (int i = 0; i < n; i++) { long long target = a[i] + C; auto L = lower_bound(a.begin(), a.end(), target); auto R = upper_bound(a.begin(), a.end(), target); ans += R - L; } if (C == 0) ans -= n; cout << ans << '\n'; return 0; }

对于每个 B，我们做两次 O(log n) 的二分，总复杂度是 O(n log n)。排序也是 O(n log n)，整体完全可控。存储上基本没有额外空间消耗，比存一个哈希表更省内存。

4.2 边界控制与 C=0 的特殊处理

这段代码里最需要注意的就是 C = 0。当 C = 0 时，target = a[i]，lower_bound和upper_bound的结果区间会包含 a[i] 自己。在循环里，每个元素都会把自己的出现次数加进去一次，所以最后要减去 n。

也可以不用最后统一减，而是在 C = 0 时按每个值分组来算：对于出现次数为 m 的值，能形成的不同位置数对是m * (m - 1)，把所有值累加起来。

if (C == 0) { long long ans = 0; for (int i = 0; i < n; ) { int j = i; while (j < n && a[j] == a[i]) j++; long long m = j - i; ans += m * (m - 1); i = j; } cout << ans << '\n'; return 0; }

这种写法避免了遍历每个元素再做减法，逻辑也更直接。不过我一般还是喜欢第一种：统一遍历，最后ans -= n，因为代码行数少，也不容易在分组时写错循环边界。

4.3 排序二分比 map 更“耐造”的原因

map 版本的原理没问题，但在某些极端情况下，unordered_map 会因为哈希冲突退化，普通 map 虽然稳定，但每个节点都要动态分配内存，常数较大。排序二分则完全不同：它只依赖数组本身，不依赖哈希函数，也不涉及额外节点的分配，性能稳定，而且容易调试。

我在本地测试过 n = 2e5、值随机的情况下，排序二分和 unordered_map 耗时几乎差不多。一旦数据带点“敌意”，排序二分的优势就出来了。所以如果只想记一种解法应对比赛，我建议优先掌握排序数组 + lower_bound/upper_bound。

5. 复杂度与选型图谱：什么时候用 map，什么时候用二分

5.1 四类解法横向对比

我整理了一个表格，方便你快速对照：

注意到四种解法的答案都必须用 long long 存。排序二分的额外优势是它不需要额外容器，直接排序原数组，内存占用最低。

5.2 哈希冲突的隐患与应对

unordered_map 在绝大多数随机输入下都很快，但它有一个隐藏问题：C++ 标准库的哈希函数对整数通常就是取余之类，理论上有被构造数据卡成同一个桶的可能。一旦所有元素都落在同一个桶里，查询就从 O(1) 退化成 O(n)。

如果你一定要用 unordered_map，可以自己做一层随机哈希，降低被卡概率。另一种办法是干脆用普通 map，红黑树的时间复杂度是稳定的 O(log n)，虽然慢一点，但不会出现奇怪的退化。对 A-B 数对这个量级来说，普通 map 完全够用，所以我不建议为了那一点常数性能去冒哈希冲突的险。

5.3 我的选型建议

如果是日常刷题或者比赛，我的第一选择是排序数组 + lower_bound/upper_bound。理由有三点：第一，逻辑简单，出错概率低；第二，不依赖哈希函数，测试环境稳定；第三，排序后的数组还能顺便处理很多后续问题，比如去重、找上下界、前缀最值等。

map 版本适合你已经很熟悉 STL、并且希望代码更“声明式”的时候使用。它把频次直接暴露在容器里，代码读起来很舒服。但学习的时候，我建议两条路都写一遍，尤其是 lower_bound/upper_bound 的写法，这个能力在很多其他题目里都用得上。

6. 实战中的细节坑：从负数和溢出说到重复元素

6.1 负数没问题，别用数组下标硬扛

有些题不会保证所有数字都是正整数。如果出现负数，普通数组计数就会非常难受。map 的键可以直接存负数，排序数组也天然支持负数，只有基于下标偏移的计数数组需要额外处理边界。

比如你开一个cnt[offset + x]，offset 要根据数据范围动态算。如果题里没有明确给出最小负数的范围，这就成了隐患。所以面对数据范围很大的 A-B 数对，老老实实用 map 或排序数组，不要自作聪明压缩下标。

6.2 C=0 时把自己匹配自己的次数扣掉

这是这道题最容易翻车的细节。很多人的第一版代码只测了 C > 0 的样例，交上去才发现 C = 0 的情况全错。问题不在于“目标值是否存在”，而在于“目标值就是自己”。

比如数组[3, 3, 3]，C = 0。按题目要求，能组成数对的位置是任意两个不同的位置，所以答案是 3 * 2 = 6。如果你直接输出 9，那就是把每个位置和自己也算了一次。用 per-element 遍历时，最优解就是最后统一减去 n；用分组统计时，则直接算m * (m - 1)。

6.3 重复值不是障碍，但用 set 就会踩

重复值是本题的常态。使用 set 会丢失频次信息，这不是 set 的 bug，而是它的设计目标本来就是“去重”。当你想统计次数时，就要立刻切换到 map 或排序数组。

还有一种常见的错误写法：先把数组去重，再对去重后的每个值判断是否存在配对，最后直接输出去重后数组的长度。这种写法在“所有值都唯一”的子任务里能过，但题目只要加几个重复值，答案立刻不对。

6.4 输入输出与溢出的提速细节

最后提醒一个工程细节：用 cin/cout 时记得加两行：

ios::sync_with_stdio(false); cin.tie(nullptr);

不加的话，输入输出可能慢到影响结果，特别是 n 很大的时候。同时，C、数组元素、答案变量都用long long。尤其是计算x + C时，如果 x 是 int，C 是 long long，虽然表达式会自动提升，但如果你只把数组开成 int，前面在cin >> a[i]时就已经截断了，后面怎么补都白搭。

7. 从 A-B 数对延伸出去：前缀和与配对计数

7.1 前缀和数组的差，本质也是 A-B 数对

A-B 数对不只是“数组里找差值”这么简单，它其实是一个更普遍的配对计数模型。最典型的延伸是求“子数组和等于 K 的个数”。

设前缀和数组为pre，那么子数组[i+1, j]的和等于pre[j] - pre[i]。我们要统计pre[j] - pre[i] == K的对数，这就是 A-B 数对，只不过数组换成了前缀和。写起来还可以用一次遍历优化：

map<long long, long long> seen; seen[0] = 1; long long pre = 0, ans = 0; for (long long x : a) { pre += x; ans += seen[pre - K]; seen[pre]++; }

这里seen[0] = 1是哨兵，表示“一个元素都没有时，前缀和是 0”。每往后扫描一个元素，就把当前前缀和当作 B，查一下有多少个历史前缀和等于pre - K，这样就能统计所有以当前位置结尾的合法子数组。

7.2 两数之和类问题的同一套路

A-B 数对和“Two Sum”其实是同一个模型。Two Sum 问的是A + B = S，你只需要把其中一个数变成S - a[i]，然后用 map 记录已经出现过的值。整个过程和 A-B 数对完全对称。

所以不要把这题当成死题。理解了“固定一个数、查另一个数”的套路后，你会在很多题里认出它：差值计数、前缀和、配对数量、树上的路径和统计，本质上都是同一套思考方式。

7.3 迁移时最容易忘的三件事

第一，哨兵状态要先放进去。前缀和问题里必须初始化seen[0] = 1，否则pre - K == 0的情况会漏掉。第二，先查询再更新。如果先把当前前缀和放进 map，再查pre - K，那么在 K = 0 时会把当前前缀和自己算成一对，结果多 1。第三，统计对象是“值”还是“位置”。A-B 数对统计的是位置对，所以频次和位置都要考虑，不能只去重了事。

我在实际写这一类计数题时，经常只用一句话提醒自己：先想清楚统计的是“存在”还是“个数”。存在性问题交给 set，个数问题交给 map 或排序后的二分区间。A-B 数对看着简单，但它把这三个工具的边界试了个遍。你如果也正卡在这题，不妨把上面那两版代码都手敲一遍，再用 C=0 和一个重复值多的样例去测，一次就能把原理记住。