洛谷题单指南-集合-P1102 A-B 数对

原题链接：https://www.luogu.com.cn/problem/P1102

题意解读：前文https://www.cnblogs.com/jcwy/p/18043197介绍了二分和双指针的做法，本文介绍hash的做法。

解题思路：

定义map<int, int> h，保存每个数+c出现的个数

同样，先将所有数由小到大哦排序

遍历每一个数x，答案累加ans += h[x]

然后把x+c个数累加h[x+c]++

最后输出答案即可

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int a[N], n, c;
map<int, int> h;
long long ans;

int main()
{
    cin >> n >> c;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++)
    {
        ans += h[a[i]];
        h[a[i] + c]++;
    }
    cout << ans;

    return 0;
}