题解 | 谐距下标对

本题若使用纯暴力解题会运行超时，故使用转换，a[i]-a[j]=i-j 也可替换为 a[i]-i=a[j]-j .统计a[i]-i的值并将其储存在map中。

将双变量问题转换为单变量问题，用一层循环即可解决问题。

#include <iostream>
#include <map>
using namespace std;
int main(){
    int n,a;
    long long sum=0;
    cin>>n;
    map<int,long long> m;
    for(int i=1;i<=n;i++){
        cin>>a;
        if(m.find(a-i)==m.end()) m[a-i]=1;
        else m[a-i]++;
    }
    for(auto [key,value]:m)
        sum+=(value*(value-1)/2);
    cout<<sum;
    return 0;
}