正经题解｜So Easy

题面大意

给出一个数组，在数组当中找到满足$i < j$ 并且$a_j - a_i = j - i$的对数，输出一共多少对。

思路解析

• 因为条件$i < j $，因此根据这个条件可以确定对数一定是从左往右选择，并且不会有对数重复选择的情况。
• 根据条件变式一下，条件为$a_j - a_i = j - i$，我们交换下未知数，可得$a_i - i = a _j - j$ 则为我们要求的答案。通过这个变式，我们可以将选取两个数字作比较的操作，变为求解得到相同数字的$a_i$有几个则为正确答案。

it : 1 2 3 4 5 6
val: 3 5 1 4 6 6

i = 1 . 3 - 1 = 2  answer = 0 , mp[2] += 1;
i = 2 , 5 - 2 = 3  answer = 0 , mp[3] += 1;
i = 3 , 1 - 3 = -2 answer = 0 , mp[-2] += 1;
i = 4 , 4 - 4 = 0  answer = 0 ; mp[0] += 1;
i = 5 , 6 - 5 = 1  answer = 0 ; mp[1] += 1
i = 6 , 6 - 6 = 0  answer += mp[4] ; mp[0] += 1

answer = 1

时间复杂度

只需要计算每个数字-自身下标的情况累加即可，时间复杂度$O(n)$

代码演示

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


int main(){
	int n;
    cin >> n;
    map<int,int> mp;
    long long answer = 0 ;
    for(int i = 0 ; i < n ; i ++ ){
        int x;
        cin >> x;
        x -= i ; // 求解自身数值-下标结果
        answer += mp[x]; // 与之前的情况配对
        mp[x] ++ ; // 当前情况+1
    }
    cout << answer << endl;
	return 0;
}