思路:哈希表的应用

pi + pj = i + j 可以得到 pi - i = j - pj,即对于每个数a[i]，查询前缀里有多少个j满足a[i] - i = j - a[j].

所以：用一个map记录当前前缀 下标 - 数值 出现次数

1. 初始化答案为0

2. 对于每个数a[i]，map里找数值 - 下标(a[i] - i)出现的次数，加到答案上

3. 更新map里i - a[i]出现的次数

代码

cpp

#include <bits/stdc++.h>
using namespace std;
int main(void) {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long ans = 0;
    map<int, int> cnt;

    for (int i = 1; i <= n; i++) {
        ans += cnt[a[i] - i];
        cnt[i - a[i]]++;
    }

    cout << ans << endl;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小红有一个长度为$n$的排列$p$，他想知道$p$中有多少个$i,j$对满足:$i< j$且$p_i+p_j=i+j$。

请你帮他算算吧。

输入描述

输入包含两行。

第一行一个正整数$n(1≤n≤200000)$，表示排列的长度。

第二行$n$个正整数$p_i(1≤p_i≤n)$，表示排列$p$。(保证输入是一个排列。)

输出描述

输出一行一个整数表示好对的个数。

样例1

输入

5
2 1 3 5 4

输出

4

说明

$P_i+p_2=1+2$，

$p_2+p_4=2+4$，

$p_i+p_5=1+5$，

$p_4+p_5 =4+5$。

共这四对。