“A-B”问题的二分、哈希、双指针写法

题目描述

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

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

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

输出格式

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

输入输出样例 #1

输入 #1

4 1
1 1 2 3

输出 #1

3

说明/提示

对于 $75%$ 的数据，$1 \leq N \leq 2000$。

对于 $100%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$，$1 \leq C < 2^{30}$。

题解

二分写法

考虑原问题是要求满足$a_i-a_j=C$的二元组个数，如果我们考虑去枚举$a_i$，那么我们只需要在原序列中找到值为$a_j=a_i-C$的个数即可。

对于一个有序的数组，满足相等值的部分必然构成一段连续的序列，那么我们可以考虑lower_bound()和upper_bound函数，可以快速找到这个连续端的左端点和右端点，也就是$a_i-C$在序列中第一次出现和最后一次出现（的后一个）的位置，把这段区间长度加上即可。

由于lower_bound()-a.begin()和upper_bound()-a.begin()是各自所求的下标，将其相减就是区间的长度。

代码实现如下：

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

using i64=long long;
using u64=unsigned long long;
using u32=unsigned;
using u128=unsigned __int128;

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int n,c;
    cin>>n>>c;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    i64 ans=0;
    for(int x:a){
        ans+=upper_bound(a.begin(),a.end(),x-c)-lower_bound(a.begin(),a.end(),x-c);
    }
    cout<<ans;

    return 0;
}

时间复杂度$O(nlogn)$

哈希写法

和上面的一样，我们遍历$a_i$，则只需要在数组中寻找$a_i-c$的个数。

那么我们可以先使用一个线性表存住序列本身，然后再使用一个map<int,int>来存住每个数对应的个数，最后依次累加即可。

代码实现如下：

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

using i64=long long;
using u64=unsigned long long;
using u32=unsigned;
using u128=unsigned __int128;

const int inf=0x3f3f3f3f;


int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int n,c;
    cin>>n>>c;
    vector<int> a(n);
    map<int,int> mp;
    for(int i=0;i<n;i++){
        cin>>a[i];
        mp[a[i]]++;
    }
    i64 ans=0;
    for(int x:a){
        ans+=mp[x-c];
    }
    cout<<ans;
    return 0;
}

由于省去了一步排序，时间复杂度$O(n)$，是时间复杂度最优算法，因为读入本身就是$O(n)$了。

双指针写法

运用上面lower_bound()和upper_bound()函数的含义，我们可以考虑维护两个指针，左指针$left$和右指针$right$。

对于排序过的数组vector<int> a而言，遍历数组，令a[left]是首个≥a[i]-c的数，令a[right]是首个＞a[i]-c的数，这样从a[left]到a[right]都是等于a[i]-c的数，则等于a[i]-c的数的个数永远是right-left，累加入答案中。

在这个过程中a[i]-c递增，因此$left$和$right$都会越来越向右。

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

using i64=long long;
using u64=unsigned long long;
using u32=unsigned;
using u128=unsigned __int128;

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int n;
    i64 c;
    cin>>n>>c;
    vector<i64> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    i64 cnt=0;
    int left=0,right=0;
    for(int i=0;i<n;i++){
        while(a[left]<a[i]-c) left++;
        while(a[right]<=a[i]-c) right++;
        if(a[i]-c==a[left]) cnt+=right-left;
    }
    cout<<cnt;
    return 0;
}

时间复杂度$O(nlogn)$，是sort()的复杂度。排序后的复杂度是$O(n)$，因为无论是左指针还是右指针都只是从头移动到了尾。