题目描述

D. Same Differences

You are given an array a of n integers. Count the number of pairs of indices (i,j) such that i<j and aj−ai=j−i.

Input
The first line contains one integer t
(1≤t≤104). Then t test cases follow.

The first line of each test case contains one integer n
(1≤n≤2⋅105).

The second line of each test case contains n
integers a1,a2,…,an (1≤ai≤n) — array a.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

Output
For each test case output the number of pairs of indices (i,j)
such that i<j and aj−ai=j−i.

样例

Example
Input
Copy

4
6
3 5 1 4 6 6
3
1 2 3
4
1 3 3 4
6
1 6 3 4 5 6

Output
Copy

1
3
3
10

aj−ai=j−i 变形为 aj-j=ai-i

#include <iostream>
#include <cmath>
#include <map> 
#include <cstring>
#include <algorithm>
using namespace std;
int t,n; 
long long res=0;
int main(int argc, char** argv){
    scanf("%d",&t);
    int x;
    map<int,int>::iterator it; 
    while(t--){
        scanf("%d",&n);
        res=0;
        map<int,int> num;//放到这就不用clear清除了，用map存不用数组存是因为后面的遍历会超时，因为for的范围会很大
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            num[x-i]++; 
        }
        for(it=num.begin();it!=num.end();it++){
            long long t=it->second;
            res+=(t-1)*t/2;
        }
        printf("%lld\n",res);
    }
    return 0;
}