P1102 A-B 数对——题解

解题思路

统计每个数值出现次数。对序列中每个作为 $A$ 的元素 $x$，能够配对的 $B$ 必须等于 $x-C$，把该值出现次数加入答案。这样每个位置上的 $A$ 都被单独计算，重复元素也能正确计数。

复杂度分析

期望时间复杂度 $O(N)$，空间复杂度 $O(N)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;long long C;cin>>n>>C;unordered_map<long long,long long> cnt;cnt.reserve(n*2+10);vector<long long>a(n);
    for(auto &x:a){cin>>x;cnt[x]++;}
    long long ans=0;for(long long x:a){auto it=cnt.find(x-C);if(it!=cnt.end())ans+=it->second;}
    cout<<ans<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n;long long C;cin>>n>>C;unordered_map<long long,long long> cnt;cnt.reserve(n*2+10);vectora(n); for(auto &x:a){cin>>x;cnt[x]++;} long long ans=0;for(long long x:a){auto it=cnt.find(x-C);if(it!=cnt.end())ans+=it->second;} cout<<ans<<'\n';return 0; }