刷算法题的人大概率都撞见过那道“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]C2。满足 A-B2 的有 (3,1)、(5,3)。如果按元素对统计只有这两对因为 A 和 B 角色互换后不满足等式如果按位置统计元素对依然是这两对但当数组里出现重复值时情况立刻复杂起来。比如 [1, 1, 3, 3]C2按位置统计就有 2×24 对。所以解题前必须确认题目数的是“值对”还是“位置对”。经典 OJ 上的“A-B 数对”一般按位置统计因为输入是数组、元素可能重复。如果题目保证元素互不相同那 set 就够用一旦允许重复计数容器 map 或排序加二分才是通用方案。1.3 数据范围决定你能用什么算法n 的量级直接决定了暴力能不能过。如果 n≤1000双重循环完全没问题到了 n10^5O(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; } }这种写法有个隐藏细节如果 C0每一对 ij 也满足条件答案会额外多出 n 个“自己对自己”的组合而且实际提交时还要处理循环顺序非常容易错。更重要的是n 到 10^5 级别就会直接超时。所以暴力只适合用来对拍、验证小数据不适合作为正式题解。2.2 map/set 的计数思想map 方案的核心是把数组里元素的出现次数存下来然后遍历数组对于每个 B查“BC”在 map 里出现了几次累加到答案。实现起来超级短mapint, 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逻辑会更简洁setint s(a.begin(), a.end()); long long ans 0; for (int x : a) { if (s.count(x C)) ans; }但要注意如果统计的是无序数对这种写法会把每对算两次。比如 [1, 2, 3]、C1遍历到 1 时找到 2遍历到 2 时找到 3答案是 2遍历到 3 时找 4 找不到所以不会重复。这个例子碰巧没有重复但一旦 C 对多组数据生效同一对 A、B 可能从两个方向各被数到一次必须小心。2.3 排序加二分的核心逻辑排序后数组变成有序的。对于每个 BA 的候选值就是一个确定的值BC。要在有序数组里快速定位这个值标准操作就是 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 只会往右移动不会回退。用两个指针维护“等于 BC 的区间范围”整体就能做到 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 数对排序后对于每个 Bkey B C统计 count累加到答案。这里的 B 可以是数组里的每一个元素也可以按“每个不同的值”只算一次。如果数组里有重复的 B 值每个 B 都要贡献 count 次所以要么遍历整个数组要么遍历去重后的值并乘以该值出现次数。3.3 迭代器减迭代器得到的类型用 vector 时两个迭代器相减得到的是 ptrdiff_t也就是 signed 类型转成 int 或 long long 都没问题。但如果你用的是 setset 的迭代器是双向迭代器不支持随机访问lower_bound 返回的迭代器无法直接相减这也是为什么这类题目统计重复值时不推荐 set 的原因。set 的 iter 差值问题是新手写这段代码最常见的编译错误之一。3.4 C 的正负号需要统一处理如果题目给的 C 是正数那么 A-B 为正意味着 A 更大直接找 BC 没问题。但有些变种题会给出可正可负的差或者要求 |A-B|C。这时候要么分类讨论要么统一转换成“寻找值相等的元素”再处理。我的处理习惯是如果需要统计 |A-B|C就固定每个 A查 A-C 和 AC 两边的数量注意去重避免 C0 时把同一对算两遍。这个细节最容易在本地测试通过、提交却 WA 的地方栽跟头。4. 完整代码与实操验证前面把思路讲得差不多下面直接给出三份可编译的代码。我全部使用 C17 编写含少量注释方便抄作业。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; vectorlong long a(n); maplong 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]。如果 xC 不存在但因为 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; vectorlong 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; setlong long s; vectorlong 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 手动构造数据验证结果为了验证上面的二分版本是否正确我造了一组数据n6C2数组为 [1, 2, 2, 3, 4, 4]。配合手算一遍B1target3等于 3 的元素个数是 1ans 1。B2target4等于 4 的元素有两个但数组里 B2 也出现了两次所以一共贡献 2×24。B2 第二次访问同样贡献 4前面的循环里已经统计过。B3target5等于 5 的没有贡献 0。B4target6没有贡献 0。B4 第二次同样贡献 0。问题来了上面的循环按每个元素遍历B2 出现了两次每次都会把 4 的两个位置都算进去所以答案是 1220005还是 14005手动模拟一下按位置统计满足 a[i]-a[j]2 的 (i,j) 对有值为 3 的元素配对两个值为 1 的位置其实这里没有重复 1、值为 4 的元素配对两个值为 2 的位置两个值为 2 的位置各对应两个值为 4 的位置所以 2×24加起来 5。程序输出也是 5。验证通过。这种小数据手算和程序输出对拍的做法是我调试这类计数题最常用的手段。只要构造出的数据覆盖了重复值基本就能抓出逻辑错误。5. 常见问题与避坑清单踩坑久了就发现这道题真正让人 WA 的往往不是算法不会而是各种边界条件和类型问题。下面按症状、原因、解法三个维度整理成表格方便速查。症状可能原因解决思路大样例答案溢出int 存不下平方级结果答案用 long long必要时中间运算也用 long long本地测试对提交 WA数对统计方向不一致明确题目按位置还是按值统计统一遍历口径set 的迭代器不能相减set 是双向迭代器改用 vector 或直接用 map 计数C0 时答案奇怪同一对 A、B 被重复统计单独讨论 C0或按位置搭配分情况去重用 unordered_map 被卡哈希冲突导致退化换 map 或排序二分别跟评测数据较劲lower_bound 传了值而不是迭代器参数用错确认函数签名前两个参数是迭代器区间5.1 重复值导致计数翻倍这是所有计数题最容易忽略的点。如果数组存在重复值比如 [2, 2, 4, 4]C2位置对统计下答案是 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 同步数据量大了会变慢。虽然这题 n10^5 级别不读快一点也基本能过但加上 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 是竞赛通用习惯建议从一开始就保持。另外题目的 C 如果给的是 int而数组元素也读入 int计算 xC 时可能发生溢出。我的习惯是读入直接存 long long所有计算用 long long避免突然爆掉。5.4 对拍验证的重要性说句掏心窝的话很多“看起来没问题”的代码一提交就 WA原因就是缺少对拍。我个人的验证流程分三步先拿题目样例跑一遍确认基本流程通再自己构造小数据包含重复值、C0、C 为负数、数组全相等这些极端情况最后如果条件允许写一个暴力程序随机生成小规模数组把暴力结果和优化算法的结果逐一比对。有了这三步绝大多数逻辑问题都能在提交前暴露出来。个人经验小结这道题的价值远远不止“AC 一道模板题”。它把“元素计数”和“有序查找”两个基础能力串在了一起。map 解法让我意识到哈希/树计数在多值统计中的威力lower_bound/upper_bound 的组合让我彻底明白“在一个区间里数出相等元素个数”的惯用姿势。后来做很多题比如统计区间内满足条件的对子、字符串子序列计数我都下意识会往“计数值 有序查找”这个方向去想。最后再分享一个小技巧如果你在考试或项目里遇到类似“统计差值为 C 的数对”的需求而数据量不大不稳定优先写排序加二分因为它不依赖哈希、不依赖元素互异、只要求数组可排序适用范围最广。map 版本适合快速写、需求简单的情况。至于 set只有当题目明确告诉你“数组元素互不相同”时才把它当作首选。这几个容器的边界弄清楚了A-B 数对这场小考就算彻底通过了。