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

对于前 3 个测试点

1≤n≤103

对于后两个测试点

1≤n≤105

所有的测试点都满足

1≤ai≤109

输入格式：

1
2
n
a1 a2 ... an

输出格式：

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

输入样例：

1
2
5
3 2 5 2 6

输出样例：

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

1
1

思路

思路与开营测试时一样

将n个数存入vector，若a[i]+i=a[j]+j，则a[i]与a[j]完美配对。于是需要标记a[i]+i，但是a[i]+i的数据过大，数组无法存储，需要使用unordered_map标记

代码

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

using namespace std;
unordered_map<long, int> book; //标记ve[i] + i出现的次数

int main() {
    int n;
    scanf("%d", &n);
    vector<long> ve;
    for(int i = 0; i < n; i++) {
        long id;
        scanf("%ld", &id);
        ve.push_back(id);
    }
    long ret = 0;
    for(int i = 0; i < n; i++) {
        ret += book[ve[i] + i]; //有与之相同的，则可配对
        book[ve[i] + i]++;
    }
    printf("%ld\n", ret);
    return 0;
}