企业官网建设流程全解析

刷算法题的人大概率都撞见过那道“A-B 数对”：给定一个含 n 个整数的数组，问存在多少对不同的 A、B，满足 A - B = C。我第一次做的时候直接上双重循环，样例秒过，提交直接超时，回头一看数据范围才反应过来。这题的知识点其实非常集中：map/set 的计数思想，以及 lower_bound/upper_bound 这两个二分查找函数。搞明白这道题，等于把“如何快速统计符合某个差值的元素个数”这条路走通了一半。今天把这几种解法聊透，顺便说说那些文档里不会写的坑。

1. 先把问题翻译成人话

拿到题目先别急着写代码，脑子里要有一个清晰的数学模型。“A-B 数对”要想不被各种边界条件绕晕，最好把它拆成两个层面：一是它到底在统计什么，二是题目要求的“数对”到底是有序还是无序。

1.1 差值统计本质上是个“配对问题”

假设数组 a 长度为 n，给定常数 C。问有多少对 (i, j) 满足 a[i] - a[j] = C。把这个等式换个写法：a[i] = a[j] + C。也就是说，对于每一个元素 a[j]，我们只关心数组里是否存在“等于 a[j] + C”的元素；有的话，每一个都能和当前的 a[j] 组成一对。

这个“配对”视角特别重要。因为一旦把问题看成配对，自然就能联想到两件事：一是暴力双重循环里隐含的重复比较，二是用容器记录“值出现次数”以便一次性统计多个配对。整个算法的思路就从这个角度展开。

很多初学者会把这道题和“两数之和”类比。两数之和关注的是“是否存在”、“下标是多少”，这题关注的却是“有多少对”、“值是多少”，区别就在一个“计数”上。一旦开始计数，重复元素就不能只当作同一个元素处理，这就是后面选 map 而不是 set 的根源。

1.2 无序还是有序，答案差一倍

题目里“不同的数对 (A, B)”这句话，在不同版本中有不同含义。有的版本把 A、B 看作集合中两个不同的元素，不管先后顺序，也就是 (A, B) 和 (B, A) 算同一对；有的版本则明确说明是“数组中的位置”，那么 (i, j) 和 (j, i) 只要满足条件都算不同。

这两类统计结果差别很大。举个例子：数组 [1, 3, 5]，C=2。满足 A-B=2 的有 (3,1)、(5,3)。如果按元素对统计，只有这两对，因为 A 和 B 角色互换后不满足等式；如果按位置统计，元素对依然是这两对，但当数组里出现重复值时，情况立刻复杂起来。比如 [1, 1, 3, 3]，C=2，按位置统计就有 2×2=4 对。

所以解题前必须确认题目数的是“值对”还是“位置对”。经典 OJ 上的“A-B 数对”一般按位置统计，因为输入是数组、元素可能重复。如果题目保证元素互不相同，那 set 就够用；一旦允许重复，计数容器 map 或排序加二分才是通用方案。

1.3 数据范围决定你能用什么算法

n 的量级直接决定了暴力能不能过。如果 n≤1000，双重循环完全没问题；到了 n=10^5，O(n²) 就是 10^10 次运算，在绝大多数 OJ 上都不可能通过。常规做法是 O(n log n) 或 O(n) 的级别。

这个约束条件应该是在动手写代码前第一眼看清楚的。我的习惯是：先看数据范围，再决定匹配哪种算法，否则容易写出“思路正确但复杂度不过”的代码。

2. 常见解法的思路拆解

这一节把能用的解法按复杂度从高到低排一遍。重点不是记代码，而是理解每种思路什么时候该用、什么时候会出问题。

2.1 暴力枚举与它的问题

双重循环的思路就是固定一个 B，内层遍历找 A。伪代码大概是：

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

这种写法有个隐藏细节：如果 C=0，每一对 i=j 也满足条件，答案会额外多出 n 个“自己对自己”的组合，而且实际提交时还要处理循环顺序，非常容易错。更重要的是，n 到 10^5 级别就会直接超时。所以暴力只适合用来对拍、验证小数据，不适合作为正式题解。

2.2 map/set 的计数思想

map 方案的核心是：把数组里元素的出现次数存下来，然后遍历数组，对于每个 B，查“B+C”在 map 里出现了几次，累加到答案。实现起来超级短：

map<int, long long> cnt; for (int x : a) cnt[x]++; long long ans = 0; for (int x : a) ans += cnt[x + C];

容器的选择上，用 map（红黑树，O(log n) 增删查）还是 unordered_map（哈希表，均摊 O(1)），取决于数据是否卡哈希。很多 OJ 上这题给的数据用 map 没问题，但 unordered_map 因为潜在冲突问题，遇到专门构造的数据反而可能退化。

set 在这里的适用场景就有限了。set 只能记录“有没有”，不能记录“有几个”。要是题目保证元素互异，那 set 确实能替代 map，逻辑会更简洁：

set<int> s(a.begin(), a.end()); long long ans = 0; for (int x : a) { if (s.count(x + C)) ans++; }

但要注意：如果统计的是无序数对，这种写法会把每对算两次。比如 [1, 2, 3]、C=1，遍历到 1 时找到 2，遍历到 2 时找到 3，答案是 2；遍历到 3 时找 4 找不到，所以不会重复。这个例子碰巧没有重复，但一旦 C 对多组数据生效，同一对 A、B 可能从两个方向各被数到一次，必须小心。

2.3 排序加二分的核心逻辑

排序后，数组变成有序的。对于每个 B，A 的候选值就是一个确定的值：B+C。要在有序数组里快速定位这个值，标准操作就是 lower_bound 和 upper_bound。

为什么不是 binary_search？因为 binary_search 只告诉你“在不在”，不告诉你“有几个”。而要统计重复元素的个数，必须拿到第一个等于该值的位置和第一个大于该值的位置，两者下标之差就是等于该值的元素个数。这两个位置的查找，正好对应 lower_bound 和 upper_bound。

排序加二分的时间复杂度是 O(n log n)（排序的 n log n 加上每个元素二分一次的 n log n），空间 O(1)（如果不算排序的栈空间）。这个方案的优点是不依赖哈希，不会被数据坑；缺点是代码比 map 长一点，但清晰度很高。

2.4 双指针为什么也适用

排序之后，除了二分，还可以用双指针扫描。因为数组有序，随着 B 增大，满足条件的 A 只会往右移动，不会回退。用两个指针维护“等于 B+C 的区间范围”，整体就能做到 O(n)。

不过双指针写起来要注意边界，特别是多个相同值同时存在的情况。二分的写法相对更不容易出错，所以我更推荐先用二分把题目过掉，再去钻研双指针。

3. lower_bound/upper_bound 的细节才是重头戏

很多题解把这题归为“练习 STL 二分”的模板题，我觉得真正值得讲的不是调函数本身，而是理解这两个函数返回值的含义，以及如何组合它们完成“区间统计”。

3.1 两个函数的行为对比

在有序容器上，函数是根据迭代器区间进行二分查找的：

• lower_bound(begin, end, key)：返回第一个“不小于 key”的元素位置，也就是 a[pos] >= key。
• upper_bound(begin, end, key)：返回第一个“大于 key”的元素位置，也就是 a[pos] > key。

注意它们对相等元素的处理完全不同。lower_bound 是“大于等于”，upper_bound 是“严格大于”。如果容器中不存在 key，两者都会指向第一个大于 key 的位置，此时它们相等，差值为 0。

这有点像在一条按身高排好的队伍里找人。lower_bound 就是问“身高 1.70 米的人第一个站在哪”，upper_bound 就是问“超过 1.70 米的人第一个站在哪”，中间那段夹着的人全部是 1.70 米。

3.2 用“区间长度”代替“直接找值”

当容器中存在重复元素时，直接找“等于 key 的个数”最通用的写法就是：

int left = lower_bound(a.begin(), a.end(), key) - a.begin(); int right = upper_bound(a.begin(), a.end(), key) - a.begin(); int count = right - left;

这个 count 就是等于 key 的元素个数。如果 key 不存在，left 和 right 会指向同一个位置，count 为 0。这个组合在后续所有解法中都会用到。

回到 A-B 数对：排序后，对于每个 B，key = B + C，统计 count，累加到答案。这里的 B 可以是数组里的每一个元素，也可以按“每个不同的值”只算一次。如果数组里有重复的 B 值，每个 B 都要贡献 count 次，所以要么遍历整个数组，要么遍历去重后的值并乘以该值出现次数。

3.3 迭代器减迭代器得到的类型

用 vector 时，两个迭代器相减得到的是 ptrdiff_t，也就是 signed 类型，转成 int 或 long long 都没问题。但如果你用的是 set，set 的迭代器是双向迭代器，不支持随机访问，lower_bound 返回的迭代器无法直接相减，这也是为什么这类题目统计重复值时不推荐 set 的原因。set 的 iter 差值问题，是新手写这段代码最常见的编译错误之一。

3.4 C 的正负号需要统一处理

如果题目给的 C 是正数，那么 A-B 为正意味着 A 更大，直接找 B+C 没问题。但有些变种题会给出可正可负的差，或者要求 |A-B|=C。这时候要么分类讨论，要么统一转换成“寻找值相等的元素”再处理。

我的处理习惯是：如果需要统计 |A-B|=C，就固定每个 A，查 A-C 和 A+C 两边的数量，注意去重（避免 C=0 时把同一对算两遍）。这个细节最容易在本地测试通过、提交却 WA 的地方栽跟头。

4. 完整代码与实操验证

前面把思路讲得差不多，下面直接给出三份可编译的代码。我全部使用 C++17 编写，含少量注释，方便抄作业。

4.1 解法一：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); 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]; } cout << ans << "\n"; return 0; }

这份代码的核心是 cnt[x + C]。如果 x+C 不存在，但因为 operator[] 会在 map 里插入一个默认值 0，所以读出来就是 0，累加无影响。需要提醒的是，不要在遍历同一个 map 的时候用 operator[] 去访问不存在的 key，因为那会改变容器大小、导致迭代器失效。这里是先建完 map，再用数组里的 x 去查，安全。

4.2 解法二：排序加二分，不依赖哈希

#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 left = lower_bound(a.begin(), a.end(), target); auto right = upper_bound(a.begin(), a.end(), target); ans += right - left; } cout << ans << "\n"; return 0; }

这份代码比 map 更省内存，而且不会受哈希冲突影响。如果 C 很大，target 可能超出 long long 范围吗？理论上数组元素和 C 都在 int 范围内就不会，但如果输入上限接近 2×10^9，相加后仍可能在 int 范围内，用 long long 存储纯粹是图个稳。

4.3 解法三：set 的适用前提

set 版本只能用于元素互异的题目设定，所以并不通用。不过如果你想练习 set 的 lower_bound，可以看这个写法：

#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; set<long long> s; vector<long long> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; s.insert(a[i]); } long long ans = 0; for (long long x : a) { auto it = s.lower_bound(x + C); if (it != s.end() && *it == x + C) { ans++; } } cout << ans << "\n"; return 0; }

这段代码假设每次配对都是唯一的。由于是互异数组，一个值最多被匹配一次，不会出现重复计数的问题。

4.4 手动构造数据验证结果

为了验证上面的二分版本是否正确，我造了一组数据：n=6，C=2，数组为 [1, 2, 2, 3, 4, 4]。

配合手算一遍：

• B=1，target=3，等于 3 的元素个数是 1，ans += 1。
• B=2，target=4，等于 4 的元素有两个，但数组里 B=2 也出现了两次，所以一共贡献 2×2=4。
• B=2 第二次访问，同样贡献 4，前面的循环里已经统计过。
• B=3，target=5，等于 5 的没有，贡献 0。
• B=4，target=6，没有，贡献 0。
• B=4 第二次，同样贡献 0。

问题来了：上面的循环按每个元素遍历，B=2 出现了两次，每次都会把 4 的两个位置都算进去，所以答案是 1+2+2+0+0+0=5？还是 1+4+0+0=5？

手动模拟一下：按位置统计，满足 a[i]-a[j]=2 的 (i,j) 对有：值为 3 的元素配对两个值为 1 的位置（其实这里没有重复 1）、值为 4 的元素配对两个值为 2 的位置，两个值为 2 的位置各对应两个值为 4 的位置，所以 2×2=4，加起来 5。程序输出也是 5。验证通过。

这种小数据手算和程序输出对拍的做法，是我调试这类计数题最常用的手段。只要构造出的数据覆盖了重复值，基本就能抓出逻辑错误。

5. 常见问题与避坑清单

踩坑久了就发现，这道题真正让人 WA 的往往不是算法不会，而是各种边界条件和类型问题。下面按症状、原因、解法三个维度整理成表格，方便速查。

5.1 重复值导致计数翻倍

这是所有计数题最容易忽略的点。如果数组存在重复值，比如 [2, 2, 4, 4]，C=2，位置对统计下答案是 4（每个 2 配每个 4）；如果题目要求的是“不同值对”，那答案就只能是 1（只有 2 和 4 这一组值对）。写 map 版本时，如果你用值去重后的集合遍历，答案会不同；如果直接遍历原数组，又是另一种答案。务必先读清楚题面。

5.2 二分查找的区间越界问题

当 target 大于数组最大值时，lower_bound 返回 a.end()，upper_bound 也返回 a.end()，二者之差为 0，看似没毛病。target 小于数组最小值时，lower_bound 返回 begin()，upper_bound 也返回 begin()，差值为 0，也没问题。真正容易出错的是你手写二分代替 STL 时，边界写错导致死循环或漏统计。所以我建议直接用 STL，不要自己造轮子，除非你在学习二分实现。

5.3 读入优化与数据溢出

cin 默认与 stdio 同步，数据量大了会变慢。虽然这题 n=10^5 级别不读快一点也基本能过，但加上 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 是竞赛通用习惯，建议从一开始就保持。

另外，题目的 C 如果给的是 int，而数组元素也读入 int，计算 x+C 时可能发生溢出。我的习惯是读入直接存 long long，所有计算用 long long，避免突然爆掉。

5.4 对拍验证的重要性

说句掏心窝的话，很多“看起来没问题”的代码，一提交就 WA，原因就是缺少对拍。我个人的验证流程分三步：

先拿题目样例跑一遍，确认基本流程通；再自己构造小数据，包含重复值、C=0、C 为负数、数组全相等这些极端情况；最后，如果条件允许，写一个暴力程序，随机生成小规模数组，把暴力结果和优化算法的结果逐一比对。有了这三步，绝大多数逻辑问题都能在提交前暴露出来。

个人经验小结

这道题的价值远远不止“AC 一道模板题”。它把“元素计数”和“有序查找”两个基础能力串在了一起。map 解法让我意识到哈希/树计数在多值统计中的威力，lower_bound/upper_bound 的组合让我彻底明白“在一个区间里数出相等元素个数”的惯用姿势。后来做很多题，比如统计区间内满足条件的对子、字符串子序列计数，我都下意识会往“计数值 + 有序查找”这个方向去想。

最后再分享一个小技巧：如果你在考试或项目里遇到类似“统计差值为 C 的数对”的需求，而数据量不大不稳定，优先写排序加二分，因为它不依赖哈希、不依赖元素互异、只要求数组可排序，适用范围最广。map 版本适合快速写、需求简单的情况。至于 set，只有当题目明确告诉你“数组元素互不相同”时，才把它当作首选。这几个容器的边界弄清楚了，A-B 数对这场小考就算彻底通过了。