蓝桥杯备赛：Day3-P1102 A-B 数对
📚 算法笔记：P1102 A-B 数对 (枚举与哈希查找)
1. 题目简述
P1102 A-B 数对 - 洛谷
给出一个长度为N NN的正整数数列和一个整数C CC，求有多少个不同的数对( A , B ) (A, B)(A,B)满足A − B = C A - B = CA−B=C。
- 数据范围：N ≤ 2 × 10 5 N \le 2 \times 10^5N≤2×105，答案可能超过
int范围。
2. 核心代码 (C++ 实现)
#include <bits/stdc++.h> using namespace std; typedef long long ll; int N; ll c; ll arr[200005]; // 存储原始数列 map<ll, ll> cnt; // 存储每个数字出现的次数 (Key:数字, Value:次数) ll ans = 0; // 最终对数，必须用 long long void solve() { // 1. 读入数据并进行安全检查 if(!(cin >> N >> c)) return; // 2. 第一次遍历：读入数组并统计每个数字出现的频率 for (int i = 1; i <= N; i++) { cin >> arr[i]; cnt[arr[i]]++; // map 自动处理：若不存在则初始化为0再++ } // 3. 第二次遍历：将每个数看作 B，寻找符合条件的 A for (int i = 1; i <= N; i++) { // 变形公式：A - B = C => A = B + C // 我们当前枚举的是 B (即 arr[i])，我们要找 A (即 arr[i] + c) // 直接从 map 中获取 A 出现的次数并累加到答案中 ans += cnt[arr[i] + c]; } // 4. 输出最终结果（注意不要写在循环内部） cout << ans << endl; } int main() { // 竞赛必备优化 ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); solve(); return 0; }3. 核心考点与注意事项
🔍 核心考点
- 公式变形：将A − B = C A - B = CA−B=C转化为A = B + C A = B + CA=B+C。这是算法优化的前提，将“寻找两个变量”转化为“固定一个变量，查找另一个变量”。
- 哈希表计数：利用
std::map实现O ( log N ) O(\log N)O(logN)的查找效率。如果使用双重for循环（O ( N 2 ) O(N^2)O(N2)），面对2 × 10 5 2 \times 10^52×105的数据量会彻底超时。 - 数据类型意识：
- 计数结果：N NN个数如果全部相同且C = 0 C=0C=0，答案是N 2 N^2N2，会爆
int。 - Key 值：输入的数字可能很大，
map的键必须用long long。
- 计数结果：N NN个数如果全部相同且C = 0 C=0C=0，答案是N 2 N^2N2，会爆
⚠️ 注意事项
- Map 的副作用：访问
cnt[x]时，如果x不存在，map会自动插入一个0。在本题中由于我们只是累加次数，不影响结果，但在某些统计总数的场景下需谨慎。 - 重复数字处理：题目求的是“数对”数量，因此必须统计频率。例如
1 1 2 2找C = 1 C=1C=1的对数，答案应为 4（每个 1 都能匹配两个 2）。
4. 易错点回顾 (My Mistakes)
- 输出位置错误：误将
cout放在了遍历B BB的for循环内部，导致输出了每一阶段的中间累加值，而非最终结果。 - 代码逻辑顺序：最初尝试在读入的同时进行匹配。纠正：这种题目最稳妥的做法是“先全部读入并统计完毕”，再进行二次遍历匹配，防止逻辑遗漏。