P1102 A-B 数对

原题链接

解法一：二分搜素

首先我们知晓A-B=C,那么A=B+C,我们只需要遍历数组中的每一个元素然后在数组中搜素a[i]+c的值是否存在即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N];
int main(){
    int n,c;
    ll sum=0;
    cin>>n>>c;
    map<ll,int> map1;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        map1[a[i]]++;
    }
    for (int i=1;i<=n;i++)
        if (map1.count(c+a[i])) sum+=map1[c+a[i]];
        cout<<sum<<endl;
}

解法二：双指针

我们先将数组按照非降序排列，我们用r1表示a[r1]-a[i]<c;r2表示a[r2]-a[i]<=c;那么对于每个a[i]我们只在需要sum+=r2-r1即可

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int a[N];
int main(){
    int n,c;
    ll sum=0;
    cin>>n>>c;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    int r1=1,r2=1;
    for (int i=1;i<=n;i++){
        while (r1<=n && a[r1]-a[i]<c) r1++;
        while (r2<=n && a[r2]-a[i]<=c) r2++;
        sum+=r2-r1;
    }
    cout<<sum<<endl;
}

Ps：如果a数组本身就是非降序的话，法二时间复杂度只有O（n）