洛谷 P1102 A-B 数对（详解）c++

题目链接：P1102 A-B 数对 - 洛谷

1.题目分析

2.算法原理

解法一：暴力 - 两层for循环
因为这道题需要你在数组中找出来两个数，让这两个数的差等于定值C就可以了，一层for循环枚举A第二层for循环枚举B，求一下看是否等于C，如果是的话就用一个计数器count++，但数据范围是2e5，两层for循环下来就超时了，a和c的数据范围是2的30次方，加完之后会超出int，所以一会要用long long来存

解法二：先统计数组中每个数出现的次数，接下来枚举所有的B，然后找出C + B出现的次数

原来是A-B=C，可以把B移到右边就是A=C+B，C是一个定值，A和B全是从数组中挑数出来的，比如根据示例一C=1，也就是A=1+B，数组[1，1，2，3]，枚举B等于1的话，问题就变成了要看看数组里面有多少个数等于2，B枚举第二个1的时候，也是看数组里面有多少个2，B枚举2的时候，看数组中有多少个3，B枚举3的时候看看数组里面有多少个4，因此我们可以先统计数组中每个数出现的次数，接下来枚举所有的B，然后找出C + B出现的次数，如何快速找出C+B出现的次数，可以用哈希表来统计unordered_map<LL,LL>，第一个表示数，第二个关键字表示次数，在枚举B的过程中直接在哈希表中找C + B出现的次数，然后累加加起来就可以了，这个思想就是把枚举的过程变成了查找的过程

代码：

#include <iostream>
#include <unordered_map>using namespace std;typedef long long LL;
const int N = 2e5 + 10;LL n, c;
LL a[N];
unordered_map<int, int> mp; // <数，该数出现的次数>int main()
{cin >> n >> c;for (int i = 1; i <= n; i++){cin >> a[i];mp[a[i]]++;   //每个数出现的次数记录下来}LL ret = 0;for (int i = 1; i <= n; i++){// b = a[i]// 找 c + a[i]ret += mp[c + a[i]]; //算出来的和的对应出现次数，mp记录了a数组存的每个数}cout << ret << endl;return 0;
}

如果这道题c可以等于0，在累加次数的代码附近加一个判断即可

#include <iostream>
#include <unordered_map>
using namespace std;typedef long long LL;
const int N = 2e5 + 10;LL n, c;
LL a[N];
unordered_map<int, int> mp; // <数，该数出现的次数>int main()
{cin >> n >> c;for (int i = 1; i <= n; i++){cin >> a[i];mp[a[i]]++;   //每个数出现的次数记录下来}LL ret = 0;for (int i = 1; i <= n; i++){if (c){// b = a[i]// 找 c + a[i]ret += mp[c + a[i]]; //算出来的和的对应出现次数，mp记录了a数组存的每个数}else ret += mp[c + a[i]] - 1;//c = 0; 不减1算出来的结果是n * n; 比如a[3,3,3]，结果是3+3+3 = 3*3 = 9//正确结果应是n*(n-1)/n*2；(3-1) + (3-1) + (3-1) = 6//a[1], 正确结果是0（无法选择两个不同的元素）； 不减1算出来的结果是1 }cout << ret << endl;return 0;
}