题解 | 谐距下标对
谐距下标对
https://www.nowcoder.com/practice/12fd032361704c978bcb9c2c2b3bb93d
本题若使用纯暴力解题会运行超时，故使用转换，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;
}
OPPO公司福利 1229人发布