企业官网建设流程全解析

P1102 A-B 数对在洛谷上被标成“普及-”，不少新手扫一眼觉得是白给题：统计差值等于 C 的数对嘛，我两层循环直接数不就行了。可真提交上去，迎面就是 TLE，这时候才开始怀疑人生。我自己带新人训练时发现，这道题其实是非常典型的“二分和双指针入门练手题”，它把“枚举位置”硬生生变成了“统计值出现次数”，思路一旦转过来，后面做两数之和、区间配对之类的问题都会顺手很多。这篇文章把我实际写过的三种解法、C=0 这个坑、以及排查超时和重复计数的完整过程都整理出来，给正在刷洛谷、或者以后要面对配对统计题型的同学做个参考。

1. 先拆题：P1102 的考点根本不在于“数对”

1.1 题目到底说了什么

题面原文很长，但核心就一句：给出一串数和一个数字 C，统计满足 A-B=C 的数对个数，并且数组中不同位置的相同数字，要算不同的数对。举个例子，数组是 [2, 1, 1, 1]，C=1，那么 A=2 这个位置，可以和三个 B=1 的位置分别组成数对，答案是 3 而不是 1。这一点非常重要，很多人第一次做就是在这里漏掉计数。

另一个容易被忽略的点是数对是有方向的：A 在前，B 在后，A-B=C。也就是说 3-1=2 是一对数对，但 1-3=-2 不是。搞清楚这点之后，问题就转化为：对于每个位置上的 A，去找数组里有没有足够多个值为 A-C 的 B。如果某个值出现多次，只要 A 的位置不同，每个组合都要算一次。

1.2 数据范围决定了你只能往 O(n log n) 想

题目给的 N 最大可以到 200000 左右，具体看洛谷原题的数据范围，反正不是几十这种小规模。两层循环枚举 i 和 j，复杂度是 n²，200000 的平方是 4×10^10。你可以简单估算一下：现代 CPU 一秒大约能跑 10^8 到 10^9 次简单运算，4×10^10 意味着至少要几十秒，TLE 是必然的。

所以这道题的核心考点根本不是“你会不会枚举数对”，而是“你会不会把枚举位置对，改成枚举一个值并快速统计另一个值出现的次数”。排序在这里是总钥匙：排序之后，所有相等的值会聚成连续的一段，一段的长度就是出现次数。配合二分查找 lower_bound 和 upper_bound，就能在 O(log n) 时间内知道任意值出现了几次，整体复杂度降到 O(n log n)。

2. 三种解法拆解：为什么排序是这道题的总钥匙

2.1 暴力枚举是第一直觉，也是验证答案的基准

先别急着鄙视暴力，写对拍的时候它反而是最有用的工具。暴力写法非常直白：

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++; } } }

这段代码在 N 很小的时候完全正确，可以用来当“标准答案”。我在实际开发验证算法时，经常让优化的程序和小数据暴力程序对拍。如果你发现优化程序的输出和暴力不一致，说明你的实现里存在重复计数或者漏计数的问题。暴力 O(n²) 虽然在正式提交时必挂，但作为测试基准，它比任何理论分析都靠谱。

2.2 排序 + 二分：统计“值”的出现次数，而不是枚举“位置”

这是最推荐掌握的解法。先对数组排序，然后遍历每个位置 i，把它当作 A，那么 B 的值就应该是 target = a[i] - c。此时只需要回答一个问题：整个排序数组中，有多少个元素的值等于 target？

为什么排序后这个问题好回答？因为排序后所有等于 target 的元素挤在连续区间里。用 lower_bound 找到第一个不小于 target 的下标 L，用 upper_bound 找到第一个大于 target 的下标 R，那么 [L, R) 这个左闭右开区间里的元素全部等于 target，个数就是 R-L。

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

为什么 C 不等于 0 的时候不用管“当前位置被算进去”的问题？因为 target = a[i] - c，当 c 不为 0 时，target 永远不等于 a[i]。也就是说，二分统计出来的那些 B 值，不可能包含当前这个 A 的位置，每个数对都是“A 在某个位置、B 在另一个位置”的有效配对。只有 c=0 的时候 target 等于 a[i] 本身，才会把当前位置也统计进去，这个问题我放在下一章细说。

2.3 同向双指针：省掉二分的常数，细节藏在指针关系里

双指针是在排序基础上进一步把统计做到 O(n) 总时间。思路还是枚举 A，找值等于 target 的区间，只不过这次维护两个指针 L 和 R，分别指向当前 target 值段的左右边界。

关键洞察是：数组是递增的，a[i] 也是递增的，因此 target = a[i] - c 随着 i 的增大单调不减。所以 L 和 R 指针只会向右移动，不会回头。总移动次数不超过 2n，外层循环 n 次，总复杂度 O(n)。

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

这里最容易写错的就是if (R < L) R = L;这一句。为什么需要？因为 target 可能突然跳过好几种值。举个例子，数组是 [1, 5, 10]，c 很大导致 target 从 2 直接跳到 6。上一轮 target=2 时，L 指向 5 的位置，R 也停在第一个大于 2 的位置，也就是 5 的位置。这一轮 target=6，L 会向右移动到 10 的位置，此时 R 还停留在 5 的位置，比 L 小。如果不把 R 拉回来，R-L就是负数，答案直接错乱。所以双指针看起来简单，实际写出来要小心这种指针关系。

2.4 哈希表计数：不排序也能做，但要小心遍历方向

如果不想排序，也可以用哈希表。先用 unordered_map 统计每个值出现的次数，然后遍历哈希表里的每个值 v，把它当作 A，那么需要的 B 就是 v-c，答案累加 cnt[v] 乘以 cnt[v-c]。

#include <bits/stdc++.h> using namespace std; int n; long long c; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> c; unordered_map<long long, long long> cnt; for (int i = 0; i < n; i++) { long long x; cin >> x; cnt[x]++; } long long ans = 0; if (c == 0) { for (auto &p : cnt) { long long k = p.second; ans += k * (k - 1); } } else { for (auto &p : cnt) { long long v = p.first; auto it = cnt.find(v - c); if (it != cnt.end()) { ans += p.second * it->second; } } } cout << ans << '\n'; return 0; }

为什么遍历哈希表时不用除以 2？因为这里遍历的是 A 的值，每个 A 值对应同一批 B 值，顺序是固定的。假设 c=2，数组里 3 出现了 2 次，1 出现了 3 次，那么遍历到 v=3 时会累加 2×3=6 个数对；遍历到 v=1 时会去找 -1，找不到，不会反向再算一次。正因为数对要求 A 是前一个数，哈希解法天然避免重复，非常优雅。

不过哈希解法在洛谷上不一定比二分快，unordered_map 的常数有时候很大，极端数据下还可能被卡。我个人的建议是：想稳妥 AC，用排序加二分；想在 Python 里少写代码，用 Counter；只有特别在意常数时才上双指针。

3. C=0 这个边界，所有解法都躲不掉

3.1 同一个位置不能既当 A 又当 B

C=0 时，题目变成统计 A=B 的数对，也就是找数组里值相等但位置不同的两个数。表面上看更简单了，但对写代码的人来说这是个陷阱。

先看最简单的场景：数组 [1, 1, 1]，C=0。正确数对应该是多少？三个位置，任意选两个不同的位置，一个当前面的 A，一个当后面的 B，所以每个无序组合有 2 种方向，总数是 3×2=6。如果用公式表示，就是某个值 v 出现 k 次时，贡献 k×(k-1)，而不是 k×k。多出来的 k 就是你拿同一个位置既当 A 又当 B 的“自我配对”。

极端情况下这个数字可以非常大。200000 个相同的数，C=0，答案是 200000×199999≈4×10^10。这个结果早就超过 int 范围了，所以答案变量必须用 long long。这也是为什么我在代码里把所有参与计数的变量都声明成 long long，宁可多占 8 字节，也不能让结果溢出。

3.2 二分和双指针为什么也要特判

二分和双指针的写法里，对每个 A 位置统计的是“整个数组中等于 target 的个数”。当 c 不等于 0 时，target 不等于 a[i]，这个统计结果天然不包含当前位置，完全正确。但当 c=0 时，target 等于 a[i]，当前 A 这个位置也被算进“等于 target 的个数”里了。

每个位置都多算了一次自己，总共多算了 n 次。所以最简单的处理不是去循环里判断跳过，而是最后统一减掉 n：

if (c == 0) ans -= n;

一小行代码，解决所有麻烦。你可以试着自己推一下：如果数组是 [1,1,1,3,3]，C=0。二分法对每位置累加统计，1 出现 3 次，三个 1 的位置各贡献 3，共 9；两个 3 的位置各贡献 2，共 4，总 13。减去 n=5，得到 8。真实答案是 cnt[1]×(cnt[1]-1)=3×2=6，加上 cnt[3]×(cnt[3]-1)=2×1=2，总共 8。完全一致。

哈希解法在 c=0 时用的是另一套分支，直接写 k×(k-1)，不需要最后减 n。两种思路都能处理，但一定要记得这个坑真的存在。我知道很多人刷这道题时测试数据全是 c>0，就觉得无所谓，结果某个隐藏测试点里 c 恰好为 0，直接 WA。别问我是怎么知道的，问就是我亲眼见过一排排红色提交记录。

4. 完整代码与逐行拆解

4.1 C++ 二分版

上面已经贴过二分版代码，我再把它拆开讲几个容易被忽视的细节。

long long a[200005];

数组开成 long long，是为了和 target 的计算保持一致。a[i] - c里如果 c 比较大，结果可能是负数，用 int 虽然也能存，但一旦数值边界比较紧，容易出现类型转换上的意外。直接全用 long long 最省心。

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

这两行是给 cin、cout 提速的。算法竞赛里很多 TLE 不是算法问题，而是输入输出慢了。200000 个整数用默认的 cin 读，某些评测机上会明显变慢，加上这两行保险很多。注意关闭同步之后，不要再混用 scanf 和 cin，否则输入顺序会乱。

二分部分lower_bound和upper_bound返回的是迭代器，减掉数组首地址a才能得到下标。左闭右开区间的长度R-L就是等于 target 的元素个数。如果 target 比数组最小值还小，lower_bound 返回 begin()，R 也等于 L，区间长度为 0，结果 0，非常自然。

4.2 C++ 双指针版

双指针版的完整代码上节已经给出，这里只强调一个工程习惯：不要一上来就写双指针。双指针的常数确实更小，但它比二分容易写错，尤其是 R 和 L 的单调关系。我的做法是先用二分版本把题目 AC，如果之后发现有性能瓶颈，或者题目要求的时间极限卡得很死，再换双指针优化。这样能保证正确性优先，不至于在调试指针关系上浪费时间。

另外双指针中，R的更新是从max(R, L)开始的，我用的写法是：

if (R < L) R = L;

如果你直接把 R 重置成 L 也可以，因为 R 本来就不小于 L，只有可能出现 R 落后于 L 的情况。这个 if 的存在就是为了处理 target 跳变。

4.3 Python 版：两种写法

Python 刷洛谷这道题，最简洁的是用 Counter 哈希法：

import sys from collections import Counter def main(): data = sys.stdin.read().split() n = int(data[0]) c = int(data[1]) a = list(map(int, data[2:2 + n])) cnt = Counter(a) if c == 0: print(sum(k * (k - 1) for k in cnt.values())) else: print(sum(cnt[v] * cnt.get(v - c, 0) for v in cnt)) if __name__ == "__main__": main()

如果想用二分，Python 需要导入 bisect 模块：

import sys from bisect import bisect_left, bisect_right def main(): data = sys.stdin.read().split() n = int(data[0]) c = int(data[1]) a = list(map(int, data[2:2 + n])) a.sort() ans = 0 for x in a: t = x - c ans += bisect_right(a, t) - bisect_left(a, t) if c == 0: ans -= n print(ans) if __name__ == "__main__": main()

两种我都实测过。Counter 写法代码量小，但哈希表的开销在数据量大时会让 Python 跑得比较吃力。bisect 写法是纯 Python 的二分，常数也不小，但胜在逻辑清晰。如果是在洛谷上提交 Python，建议数据量大时优先考虑 bisect 版本，或者干脆用 PyPy 跑 Counter 版本，效果通常可以接受。

4.4 用对拍验证：暴力 + 随机数据，把坑提前揪出来

写完代码别急着交，用对拍验证是最稳的。特别是这道题有 C=0 的坑，手算几组样例根本想不全面。我建议准备三个文件：gen.py 生成随机小数据，brute.py 用暴力 O(n²) 算标准答案，fast.py 放你要测试的优化算法。随机生成时把数据范围故意调小，但让 C 包含 0，让重复值经常出现，这样能最大概率踩中边界。

gen.py：

import random n = random.randint(1, 10) c = random.randint(0, 10) # 故意包含 0 print(n, c) print(' '.join(str(random.randint(0, 20)) for _ in range(n)))

brute.py：

n, c = map(int, input().split()) a = list(map(int, input().split())) ans = 0 for i in range(n): for j in range(n): if a[i] - a[j] == c: ans += 1 print(ans)

然后写一个循环脚本跑几百次：

for i in $(seq 1 500); do python3 gen.py > data.txt python3 brute.py < data.txt > out_brute.txt python3 fast.py < data.txt > out_fast.txt if ! diff -q out_brute.txt out_fast.txt > /dev/null; then echo "WA on test $i" cat data.txt break fi done

一旦某个数据点两边输出不一致，把 data.txt 打出来，你就能精确复现出错场景。我用这招抓到过很多“以为写对了，其实边界漏了”的问题。对拍这个方法，强烈建议每个人都养成习惯，尤其是刷这种边界条件多的题。

5. 从 A-B=C 到 A+B=C：这类配对统计题的通法

5.1 换成 A+B=C，双指针思路会怎么变

P1102 的套路核心是“枚举一个数，统计另一个数出现次数”。这个思路稍加变形就变成另一类经典题：求无序数组中有多少对 i<j 满足 a[i]+a[j]=C。

如果还是用哈希，那逻辑几乎不变：遍历数组时维护一个 map，对每个当前元素 x，查找 C-x 在之前出现过几次，累加答案，再把 x 的出现次数加一。

如果改用排序双指针，思路就完全不一样了。因为两个数相加等于 C，一个在左一个在右，所以可以用左右双指针从两端往中间走。左指针指向数组开头，右指针指向数组末尾，根据 a[l]+a[r] 与 C 的大小关系决定移动哪边。这和 A-B=C 的同向双指针不同，因为“差”具有方向性，而“和”是对称的。

5.2 从“数对”到“区间子数组”的延伸

P1102 本身考的是值配对，但它的统计思想可以延伸到区间问题。比如给定数组，统计有多少对下标 (i,j) 满足 i<j 且 a[j]-a[i]=k，这其实就是把数对限制成“后面的数减前面的数”，排序之后的反转版本。

另一个常见变式是“统计和为定值的子数组个数”，通常用前缀和加哈希表一次遍历解决。表面上看和 P1102 没什么关系，但底层逻辑都是：把问题的某个量转成可快速查询的形式，再借助哈希或排序把 O(n²) 降到 O(n) 或 O(n log n)。理解了这一层，刷题时就不必每个题都从零开始想了。

5.3 我对这道题的理解和使用场景

以我自己的刷题习惯来说，P1102 这样的题很适合拿来当“算法思维热身”。它不涉及复杂数据结构，也没有高深的数学，但恰恰能把“枚举位置”和“枚举值”的区别讲透。每次看到“统计满足某种关系的数对”的题目，我第一反应永远是：能不能先把数组排序，把配对关系转化成可以在有序序列上快速查询的问题。

如果实在想再深入一步，建议把哈希法、二分法、双指针法都各写一遍，并且尝试在 C=0 时互相验证。写完之后你会明显感觉到，三种方法本质是在同一道题上，用自己的方式回答同一个问题：“数组里某个值到底出现了几次”。把这个问题的答案搞清楚，P1102 就真正吃透了。