题解：AT_abc417_c [ABC417C] Distance Indicators

题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1, A_2, \ldots, A_N)$，求满足 $1 \le i < j \le N$ 且 $j - i = A_i + A_j$ 的整数对 $(i,j)$ 的数量。

输入格式

• 第一行包含一个整数 $N$
• 第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$

输出格式

输出满足条件的整数对数量

解题思路

将原式 $j - i = A_i + A_j$ 变形为： $$j - A_j = i + A_i$$

使用哈希表记录遍历过程中遇到的 $i + A_i$ 值出现的次数。对于每个位置 $j$：

1. 计算 $val = j - A_j$
2. 将哈希表中 $val$ 对应的值累加到答案
3. 将 $j + A_j$ 存入哈希表

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n; // 读取序列长度
    vector<int> a(n); // 定义序列数组
    
    // 读取序列元素
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    unordered_map<int, int> m; // 哈希表，记录i+A_i出现的次数
    ll res = 0; // 结果计数器
    
    // 遍历序列中的每个元素（注意题目中i,j从1开始）
    for (int j = 0; j < n; j++) {
        // 计算j+1 - A_j（因为数组下标从0开始，题目中从1开始）
        int val = (j + 1) - a[j];
        
        // 累加之前出现过的i+A_i等于当前val的次数
        res += m[val];
        
        // 计算当前j+1 + A_j，存入哈希表供后续查询
        int key = (j + 1) + a[j];
        m[key]++;
    }
    
    cout << res; // 输出结果
    return 0;
}