题解 | 谐距下标对

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

// 键值对分组的依据是值是否相同。
    unordered_map<int, long long> count_map;
    for (int i = 0; i < n; i++) {
        int key = arr[i] - i;
        count_map[key]++;
    }

// 计算最终输出，先对一组键值对求组合数，再求所有组键值对。
    long long result = 0;
    for (const auto& [key, value] : count_map) {
        result += value * (value - 1) / 2;
    }

    cout << result;
}
// 64 位输出请用 printf("%lld")

1. 简单方法：平方时间复杂度的方法更简单，但会超时。
2. 内存溢出：如果把value声明为int，用value计算result的时候，中间结果默认是int，于是会导致内存溢出。所以把value声明为long long才可以。
3. 哈希表：本题用到哈希集合来记录数据，先是用了一个小小的恒等变换，把问题变成找元素与脚标之差相等的元素有几对。然后以元素与脚标之差为键，以出现的次数为值，把这些数据储存到哈希表里。
4. const auto&：这个auto是自动适配的意思，编译器根据上下文自动确定count_map中元素的类型。const表示值不可修改，&表示形成引用，避免拷贝pair。「const + &」一般是默认使用的，将权限限制为「只读」。