2022-03-28每日刷题打卡

代码源——每日一题

A-B 数对 - 题目 - Daimayuan Online Judge

输入格式

输入共两行。

第一行，两个整数 N, C。

第二行， N 个整数，作为要求处理的那串数。

输出格式

一行，表示该串数中包含的满足 A−B=C 的数对的个数。

样例输入

4 1
1 1 2 3

样例输出

3

数据范围

1≤N≤2×10^5, 1≤C≤2×10^5, 题目保证输入的 N 个数范围小于 2^30。

关于这题，如果我们按照题目说的找a和b来看看他们的差是否等于c，这样是相当麻烦的，相当于我们枚举A，其他的数当成B，进行计算看是否差值等于C，这样的时间复杂度是n^2，不用想肯定超时。所以我们要把问题转化一下：

我们不知道数组里有哪些数可以和我当前枚举的数相差为C，但我们知道，我们当前枚举的数-c后得到的数是什么，那么我们只要看数组里有没有这个数，如果有，那就可以组成一个数对了，如果这个数有X个，那说明可以组成X个数对。

先用哈希表跑一遍数组，记录每个数字的出现次数，然后再跑一边数组，看当前元素-c的数值是否在哈希表中被记录过，如果有，则计数器加上哈希表记录的值。最后输出计数器记录的值即可。

（其实也可以枚举b，然后看b+c的值有没有记录也行，只是个人喜欢加法）

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>#define endl '\n';
typedef long long ll;
typedef pair<ll, ll>PII;int main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n,k,res=0;cin >> n >> k;vector<int>v(n);map<int, int>mymap;for (int i = 0; i < n; i++){cin >> v[i];mymap[v[i]] ++;}for (int i = 0; i < n; i++){if (mymap[v[i] - k] != 0){res+=mymap[v[i]-k];}}cout << res << endl;return 0;
}