给定一个长度为 n 的整数序列 a1 , a2 , … , an。我们称一个二元组(i,j)是完美配对的，当且仅当 i<j 并且 ai−aj=j−i.求完美配对的二元组数目.

对于前 3 个测试点

1≤n≤103

对于后两个测试点

1≤n≤105

所有的测试点都满足

1≤ai≤105

输入格式：

1
2
n
a1 a2 ... an

输出格式：

输出完美配对的二元组数目

输入样例：

1
2
5
3 2 5 2 6

输出样例：

仅有一对二元组（1, 2）满足条件， 因为 3 - 2 = 2 - 1.

1
1

思路

暴力循环会超时

只要两个元素满足ai−aj=j−i，即ai+i=aj+j，元素数+索引数相等即可配对

开数组标记每个元素的元素数+索引数的和，扫描给定数组，每扫描一个数，寻找前面已扫描过的满足ai+i=aj+j的数量即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>

using namespace std;

const int N = 1e6 + 5;
int arr[N], num[N];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
    int ret = 0;
    for(int i = 1; i <= n; i++) {
        ret += num[arr[i] + i]; //前面满足条件的数
        num[arr[i] + i]++; //标记进去
    }
    cout << ret << endl;
    return 0;
}