“A-B”问题的二分、哈希、双指针写法
本文最后更新于 2025年3月4日 上午
引用
题目描述
给出一串正整数数列以及一个正整数 $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)$，因为无论是左指针还是右指针都只是从头移动到了尾。