P1102 A-B 数对

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

方法1：二分答案

#include<bits/stdc++.h>
using namespace std;
int n, c, a[200005];
long long ans;
int main()
{
	cin>>n>>c;
	for(int i=0; i<n; i++)
		cin>>a[i];
	
	sort(a, a+n);
	
	for(int i=0; i<n; i++){
		ans+=(upper_bound(a, a+n, a[i]+c)-a)-(lower_bound(a, a+n, a[i]+c)-a);
	}
	
	cout<<ans;
	
	return 0;
 } 

方法2：哈希表

#include<cstdio>
#include<iostream> 
#include<map>

using namespace std;

int a[200005];//桶存储每个出现过的数的次数 
map<int,int> tong;

int main()
{
	int n,c;
	scanf("%d%d",&n,&c);
	for(int i = 1;i <= n;++ i)
	{
		scanf("%d",&a[i]);
		tong[a[i]] ++;//计数 
	}
	long long js = 0;
	for(int i = 1;i <= n;++ i)
 	{//这里倒着想不去找两个数而是找一个然后再找另一个 
 		js += tong[a[i] + c];
	}
	printf("%lld\n",js);
	return 0;
 }