企业官网建设流程全解析

1. 项目背景与问题本质

做算法题的人应该都有这种感觉：有些题目一看就有思路，但一写就错；有些题表面上是数学题，骨子里却是排序题；还有些题名字挺吓人，实际上核心知识就一两个。P1102 A-B 数对就属于那种把简单道理藏得比较深、特别考验“转化能力”的题目。

先看题目在说什么。给定一个正整数序列和一个整数 C，要求统计所有满足 A - B = C 的数对 (A, B) 的数量。注意这里 A 和 B 都是序列中的元素，A 可以等于 B，同一对数字只要下标不同或者取值组合不同都要分别计数。换句话说，这不是问“存在不存在”，而是问“有多少种组合方式”。

先说结论：这道题的核心考点是“用哈希表或排序把双重循环降成单重循环”。暴力做法是两两枚举，复杂度 O(n^2)，题目给的数据范围 n 可以达到 2×10^5，平方复杂度直接超时。所以正确的打开方式是：先把数组排序，然后用双指针或者哈希表统计每个数出现的次数，再对每个 A 直接查 A - C 有多少个。

为什么强调“转化”这两个字？因为 A - B = C 移项一下就变成 A = B + C。如果你从 B 的角度出发，问题就变成“对于每一个 B，统计序列中有多少个 B + C”。这种重新关联视角的能力，恰恰是算法题最常考的东西。很多新手会死磕双重循环，不是不会写代码，而是没意识到数学恒等变形能直接改变解题复杂度。

这道题在洛谷上是普及/提高-的难度，经常出现在排序、二分、哈希的练习列表里。它本身不涉及高深的算法，但对代码实现细节要求不低。我见过不少人思路完全正确，结果因为边界条件或者计数方式写错，提交后一片 WA。下面我从头到尾把这道题的几种做法拆开讲清楚，包括为什么选型、复杂度怎么算、代码怎么写、容易踩哪些坑，最后再聊一些和它相关的高频考点，比如“最优簇数”“并发数”“宽带会话数”这些热搜词为什么会和算法题产生联系。

2. 核心思路与方案选型分析

2.1 暴力枚举为什么不行

既然题目要求统计数对数量，最直觉的做法当然是两层循环：

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

看起来没毛病，而且对于小数据完全正确。问题出在规模上。n = 2×10^5 时，n^2 = 4×10^10 次操作，普通 OJ 一秒大概只能跑 10^8 量级，直接超时到天荒地老。更别说万一出题人把 n 加到 10^6，那连想都不用想。

所以暴力解法不行的根本原因是“比较的次数太多”。我们要想办法减少比较次数，最好能把比较次数从 n^2 降到 n 或 n log n。这就要用到预处理：先把每个数的出现次数记录下来，然后一次循环解决问题。

2.2 哈希表做差法

思路很简单：用哈希表（C++ 里是 unordered_map，Python 里是 dict）存储每个数出现的次数。然后遍历每个数 B，去查找 B + C 的出现次数，累加到答案里。

为什么是 B + C？因为 A - B = C，所以 A = B + C。对每个 B 来说，如果序列中真的有 B + C 这个值，那么有多少个 B + C，就能组成多少个不同的数对。比如序列是 [1, 1, 2, 3]，C = 1，那么 B = 1 时，B + C = 2，序列中有 1 个 2，所以贡献 1；B = 1 再次出现，又贡献 1；B = 2 时，B + C = 3，贡献 1。总计 3 对数对。

哈希表做法的复杂度是 O(n)，空间复杂度 O(n)。这是理论上最优的时间复杂度，因为每个数至少要看一遍。

2.3 排序加双指针法

另一种常见做法是先排序，然后用双指针维护“B + C”的区间。排序后数组有序，对于每个 B，B + C 的位置可以用二分查找确定，也可以维护两个指针从左往右滑动。

这种做法的复杂度是 O(n log n)，主要花在排序上。优点是代码不依赖哈希表，在某些不支持高效哈希的环境下更稳，也不会因为哈希碰撞导致最坏情况退化。缺点是比哈希表稍微绕一点。

2.4 方案对比与个人倾向

个人实战中更推荐哈希表，理由很现实：写起来最快，不容易出边界 bug，而且 C++ 的 unordered_map 在大多数 OJ 上表现足够好。至于排序双指针，适合那些希望省内存或者应对严格评测环境的情况。两种都要会，因为题目的变种可能会限制不能用哈希表。

3. 哈希表解法的完整实操与原理拆解

3.1 从公式到代码的完整推导

先把公式写清楚：A - B = C，等价于 A = B + C。这里 C 是输入的固定值。我们遍历数组时，把每个元素当成 B，然后看 B + C 在数组里出现过几次。换个角度，也可以把每个元素当成 A，看 A - C 的出现次数。两种方式等价，但注意不要混用。

用第一个角度写伪代码：

map = {} for x in arr: map[x] += 1 ans = 0 for x in arr: ans += map[x + C] print(ans)

注意直接写 map[x + C] 在 C++ 里有个坑：如果 x + C 不存在，operator[] 会默认插入一个值为 0 的元素。这在逻辑上不影响答案，但会意外地向 map 中增加大量键，导致内存膨胀和性能下降。所以应该用 find 来查询：

#include <bits/stdc++.h> using namespace std; int main() { int n, C; cin >> n >> C; vector<int> a(n); unordered_map<int, int> cnt; for (int i = 0; i < n; i++) { cin >> a[i]; cnt[a[i]]++; } long long ans = 0; for (int x : a) { auto it = cnt.find(x + C); if (it != cnt.end()) ans += it->second; } cout << ans << endl; return 0; }

为什么要用 long long 存答案？因为最极端的情况是数组全部相同且 C = 0。此时任意两个元素都能组成数对，总共有 n × n 种组合。n = 2×10^5 时，n^2 = 4×10^10，远超 int 的 2^31-1 上限。所以答案变量必须用 64 位整数，否则会溢出，WA 得莫名其妙。这一条是本题最隐蔽的坑。

3.2 C = 0 的特殊场景处理

刚才说到 C = 0 的极端情况，这里展开分析一下。当 C = 0 时，条件 A - B = 0 变成 A = B，也就是说所有相同元素之间的任意配对都成立。如果某个数出现 k 次，它能贡献 k × k 对数对。哈希表的做法自动覆盖了这个场景：遍历每个 B，查 B + 0 = B 的出现次数，也就是 k，于是总贡献就是 k × k。

那如果使用排序双指针或二分的写法，遇到 C = 0 时需要特别小心。假设你在找 B + C 的右边界，C = 0 时右边界就是 B 自己的位置，如果指针移动规则写得不对，可能漏掉计数或者重复计数。所以用非哈希方法时，C = 0 必须作为特例专门处理。

哈希表本身没有这个烦恼，因为统计频率天然支持 A 等于 B 的情况。这也是我推荐哈希表的原因之一：不需要额外特判，代码的普适性更强。

3.3 双指针做法的核心细节

如果你执意想练习排序后的算法，我给出一个完整而且经过测试的版本：

#include <bits/stdc++.h> using namespace std; int main() { int n, 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; int l = 0, r = 0; for (int i = 0; i < n; i++) { // 移动 l 到第一个 >= a[i] + C 的位置 while (l < n && a[l] < a[i] + C) l++; // 移动 r 到第一个 > a[i] + C 的位置 while (r < n && a[r] <= a[i] + C) r++; ans += r - l; } cout << ans << endl; return 0; }

这里的核心是维护一个区间 [l, r)，其中所有元素都等于 a[i] + C。由于排序后数组单调递增，l 和 r 都只会向右移动，整体复杂度是 O(n)，加上排序的 O(n log n)，总复杂度为 O(n log n)。

注意 l 和 r 不会递减，这保证了双指针的线性移动。但要注意 i 循环中 a[i] + C 可能溢出 int，所以数组要用 long long 存储，尤其在 C 为负数的时候，这个隐患很明显。

3.4 为什么哈希表时间复杂度是 O(n) 却仍然有隐患

从理论上讲，unordered_map 的插入和查找平均是 O(1)，所以整体 O(n)。但 C++ 标准库的哈希表最坏情况下会退化成 O(n)，比如当所有元素都映射到同一个桶时。虽然自带哈希函数对整数几乎不会出现这种退化，但如果你硬要用字符串作为 key，或者自定义了糟糕的哈希函数，那就另当别论。

另外，unordered_map 的常数比较大，对于 n = 2×10^5 完全没问题，但如果 n 到 10^6 或者更大，哈希表的空间占用和常数开销就会显现。此时排序+双指针可能跑得更快，因为 std::sort 的常数非常小，双指针扫描也是连续内存访问，缓存友好度远高于unordered_map。

这里分享一个个人经验：在题解区经常能看到有人用 map（红黑树）代替 unordered_map，其实没必要。map 的插入和查找是 O(log n)，总复杂度 O(n log n)，虽然也能过，但常数比 unordered_map 大不少。写题时最好坚持用 unordered_map，如果你发现评测机对 unordered_map 不友好，再换回排序解法。

4. 排序与二分：思路演进的进阶解读

看完整张地图就清楚：哈希表是“查字典”，排序+二分是“查书架”。两种思路各有各的适用场景，掌握其中任何一种都能解决 P1102，但理解两种思路的差异，对以后做更复杂的计数类问题很有帮助。

排序+二分的思路是这样的：把数组排好序后，对于每一个 A，我们要快速统计序列中有多少个 A - C。由于数组有序，可以用 lower_bound 和 upper_bound 找到 A - C 的区间长度。这段长度就是当前 A 能匹配的 B 的数量。

#include <bits/stdc++.h> using namespace std; int main() { int n, 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; int l = lower_bound(a.begin(), a.end(), target) - a.begin(); int r = upper_bound(a.begin(), a.end(), target) - a.begin(); ans += r - l; } cout << ans << endl; return 0; }

这段代码最需要注意的是 lower_bound 和 upper_bound 的返回值类型。它们返回的是迭代器，减掉 a.begin() 得到下标。区间 [l, r) 是所有等于 target 的元素。如果 target 根本不存在，那 l == r，贡献为 0。

很多解释会把这种解法描述为“对每个 A 查 B”，但如果你反过来想，就是“对每个 B 查 A”。两种角度完全等价，因为公式的对称性。我更喜欢以 A 为主导理解：固定 A 查 B，这样 target = A - C 更直观，也更容易避免正负号错误。

排序+二分的一个小优点是不用额外存储频率，原地修改数组后就可以操作，空间复杂度只有 O(1)。缺点是 lower_bound 和 upper_bound 各自都要走一遍二分，每个 A 做两次 O(log n) 查询，常数比双指针大一点。不过对本题的数据范围来说，性能没有本质差异。

延伸思考：如果题目变成“统计 i < j 且 a[i] - a[j] = C 的有序数对”，排序+二分的代码可能就不适用了，因为排序破坏了原始下标关系。这时候要用分治或树状数组。所以做算法题千万不要死记模板，要想清楚下标顺序在题目里到底重不重要。P1102 不要求 i < j，只要求两个数本身满足差值，所以排序没问题，这也正是题目设计的关键条件。

5. 常见问题与实测排查记录

这部分是我实际刷题和刷题群里最常见的提问整理，专门挑那些题解里不太会写、但实战中一定会遇到的问题。

5.1 答案超 int 范围

这个坑排第一，因为 wa 的概率极高。你一眼看去答案好像不会很大，但你想象一下：n = 2×10^5，C = 0，数组全是同一个数，那答案就是 4×10^10，这在 int 范围内完全放不下。所以答案变量务必声明为 long long。C++ 中计算时也要注意，如果 ans 是 int，即使 += 右边的表达式是 long long，ans 自身溢出还是会丢精度。正确做法就是从一开始就用 long long ans = 0。

5.2 unordered_map 的 operator[] 引起性能退化

我见过不少写法这样写：

for (int x : a) ans += cnt[x + C];

代码很简洁，但问题在于 cnt[x + C] 若不存在，就会插入一个默认零值。一旦数组里不同的 x + C 特别多，unordered_map 会被插入大量无用键，不仅拖慢速度，还可能触发扩容，造成严重的性能下降。正确做法是用 find 或 count 先判断。实测中这个坑在小数据上完全没感觉，数据一大就卡死。

5.3 使用 int 读入和存储数值时的溢出

如果题目允许 C 为负数，或者 a[i] 接近 int 边界，那么 x + C 在 int 计算时可能溢出，产生未定义行为。建议读入数组时直接使用 long long 存储，计算 target 时也保持 long long。排序和二分照常工作，对结果无影响。

5.4 双指针版本 C = 0 时的死循环风险

有些双指针版本在 C = 0 时会陷入死循环，因为寻找等于 a[i] 的区间时，左右指针可能不动，而 i 又向前推进，看起来没问题，但如果你用 while 写错了循环条件，可能在 l < n && a[l] < a[i] + C 这里反复判断。我建议严格用上面给出的模板，l 和 r 的控制条件写清楚。

5.5 输入输出优化

当 n 较大时，cin/cout 默认同步模式较慢，可能拖慢整体速度。C++ 选手可在 main 开头加上：

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

这道题 n 不大，加不加都能过，但从第一次写题就养成习惯是好事。不光是 P1102，许多 O(n log n) 或 O(n) 的题，输入量达到 10^6 时，这个优化可能是 AC 和 TLE 的分水岭。我举个例子：曾经在别的题目里，n = 5×10^5，不加这行代码实测慢 30% 左右，加上后稳稳通过。

6. 延伸思考：从一道题看“计数类算法”的通用套路

6.1 哈希计数与“最优簇数”是什么关系

搜题时你可能看到“最优簇数”“并发数”这些热搜词。它们看起来和 P1102 毫无关系，实际上背后是同一个底层能力：对大量数据进行统计和聚合，然后根据统计结果做判断。在机器学习里，“最优簇数”就是选取 KMeans 的 K 值，需要遍历不同 K 计算簇内距离之和，然后找到拐点；在系统性能里，“并发数”代表同时处理的请求数量，需要压测统计吞吐量曲线。所有这些场景的第一件事都是“统计频率”，和哈希表查 A - B 有着相似的思维结构。

客观来说，P1102 这类题目教给你的不是数学题本身，而是“建立一个查找表，让原本需要遍历才能确认的关系变成 O(1) 查询”。这种思想在数据库索引、缓存设计、MapReduce 的 count 阶段里面都能看到对应的影子。

6.2 从“宽带会话数4096”和“数仓建模”看统计约束

热搜词里有一类特别有意思：“宽带会话数4096是什么意思”“1000兆宽带限制会话数”。会话数本质上是网络设备或服务器能同时维护的连接数上限。这个上限取决于资源和管理策略，比如一张哈希表能开多少个桶、一台路由器能记多少条 NAT 映射，都和“容量规划”有关。而 P1102 的 n 上限同样是容量限制：题目把 n 设计成 2×10^5，就是为了引导你用一个能处理海量键值统计的解法。

“数仓建模”则更贴近另一层：在数据仓库里，你要建立维度表和事实表，核心就是通过键值关联完成聚合统计。P1102 的 A - B 数对其实就是最简化的“两表关联”模型。一张表叫 A，一张表叫 B，关联条件是差值等于 C。你用哈希表做关联，相当于在数仓里做一次 Hash Join；你用排序双指针做关联，相当于 Sort Merge Join。数据库优化器里这两个 join 策略的选择逻辑，恰好就是这道题的两种解法。

这样看，一道竞赛题，背后映射的是大数据领域实实在在的工程问题。这也是我说算法题不是刷过就扔，而是要理解其思想的原因。

6.3 如果题目稍作变形，你能应对吗

把这道题稍微改动一下，就变成了另一道很经典的题：给定序列，统计有多少对 (i, j) 满足 i < j 且 a[i] + a[j] = C。这就是“两数之和”的计数版。解法依然是哈希表：遍历每个元素 x，先查 C - x 出现次数，累加答案，再把 x 的计数加一。注意这里必须“先查再插”，否则会把同一个元素和自己配对，造成重复计数。

再改一下：给定序列，统计多少对 (i, j) 满足 i < j 且 a[j] - a[i] = C，也就是“差为 C 且位置有序”。解法也不需要复杂数据结构，从右往左遍历时维护一个哈希表，记录已出现的右边元素，对于当前元素 a[i]，查 a[i] + C 的个数即可。

这些变种题都在考察“动态维护频率”的能力。P1102 不带位置约束，所以你可以先统计全局频率再统一计算；带上位置约束后，就得一边扫描一边更新频率。理解了这个递进关系，你会发现自己不只是在刷题，而是在构建一套处理“序列计数问题”的思维框架。

6.4 聊聊“数电模电”和“梅森数”——跨领域的思维共振

热门搜索词里混杂着“数电模电基础知识”“7-15 梅森数”“卡特兰数”之类的内容。可能你会觉得这些完全不相关，但如果你从“计算思维”的角度看，它们有一个共同点：都要处理离散对象的组合和计数。数电里的真值表统计、模电里的带宽设计、梅森数的质数判定、卡特兰数的组合计数，本质上都是“在离散空间里进行系统枚举或公式推导”。P1102 只是把这种能力放到最朴素的整数序列上训练一遍，后面你会发现在任何领域做数据分析都离不开这些基本功。

7. 最后经验和刷题建议

这道题我至少在不同场合讲过三四遍，每次讲完都有人恍然大悟。这里再总结几点个人体会。

第一，拿到题先不要急着写代码。先花一分钟把公式变形写下来，想清楚“谁是已知量，谁是查找目标”。P1102 你把 A - B = C 变成 A = B + C，代码闭着眼都能写对；反过来如果你在代码里迷迷糊糊地用 cnt[x - C] 查，也能过，但容易搞混逻辑，改 bug 时特别痛苦。

第二，写哈希表代码时，务必养成 find 的习惯。虽然 operator[] 写起来爽，但副作用很大。不光是这道题，任何用哈希表计数的题目都应该遵守这条纪律。用久了你会发现，find 比 operator[] 更能避免隐式插入，代码的可读性也更高。

第三，答案类型用 long long 这个习惯要刻进 DNA。很多计数题表面上答案不大，出题人随便构造一个全等数列就把 int 秒了。比如 n = 10^5，C = 0，答案就是 10^10。竞赛里 C++ 选手被 int 溢出坑掉的次数，估计比被算法难倒的次数还多。

第四，如果可能，把哈希表解法、排序双指针解法、排序二分解法三种都亲手写一遍。不要觉得浪费时间，因为它们在数据结构课程里对应三种不同的视角。很多面试官喜欢追问“还有没有别的解法”，如果你能从头推导出双指针的单调性，说明你是真的理解了排序的作用，而不是背题解。

第五，刷完这道题后，建议继续做两道同类型巩固。比如力扣上的“两数之和”“三数之和”计数变种，还有洛谷上的其他哈希统计题。做题后把思路写下来，比光刷题有效得多。我就是这么练习过来的：每道有价值的题都会写一小段思路笔记，时间长了会发现，自己对“计数类问题”的直觉越来越准，很多题一眼就能看出该用哈希还是排序。

最后分享一个实际操作中的小技巧：如果你在本地测试时总是分不清到底是超时还是答案错误，可以写一个针对小数据量的暴力解法，生成随机数据做对拍。拿 P1102 来说，暴力枚举和哈希表解法对 n = 100 的随机数据输出应该完全一致。对拍几次，基本上能快速验证新算法的正确性，再提交就不会反复 WA 了。

P1102 A-B 数对不算难题，但它把“数学恒等变形、数据结构选型、类型溢出、常数优化”这些细节完美结合起来。把它彻底吃透的收获，远不止过一道题这么简单。希望这篇文章能帮你少踩几个坑，也让你体验到“把一道简单题做深”的乐趣。