题目来源:计蒜客5.24训练联盟周赛
Every day a new programming problem is published on Codehorses. Thus, n problems will be published in the following n days: the difficulty of the i-th problem is ai. Polycarp wants to choose exactly three days i, j and k (i < j < k) so that the difference of difficulties on the day j and the day i is equal to the difference of difficulties on the day k and day j. In other words, Polycarp wants equality aj −ai = ak −aj to be true. Determine the number of possible ways for Polycarp to choose the three days in the desired way.
Input
The first line contains an integer t — the number of test cases in the input (1 ≤ t ≤ 10). Then t test case descriptions follow. The first line of a test case contains an integer n — the number of the days (3 ≤ n ≤ 2000). The second line of the test case contains n integers a1,a2,...,an, where ai is the difficulty of the problem on the i-th day (1 ≤ ai ≤ 109).
Output
Output t integers — the answers for each of the test cases in the input, in the order they are given. The answer to a test case is the number of triples of indices i, j, and k such that 1 ≤ i < j < k ≤ n and ak −aj = aj −ai.

题意：枚举满足ak −aj = aj −ai的i, j, k有几组。
题记：我一开始是枚举i,j的全部组合，然后再去找k，复杂度分析错了(i,j的话所得组合数依然是n^2,最后总复杂度还是n^3)。师哥一种优化思路，枚举j，k，在枚举j的过程中，可以把<j的放到map里(也就是可以取的i),这样的话，在枚举j,k的时候就可以利用map自带的"二分查询"(mp.count())来把枚举i的时间复杂度O(n)降低到O(logn)。顺便还听说了一个东西叫unordered_map<>, 好像在查询这方面比map更有效率一些。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+7;
int a[N];
inline ll read(){
    char c=getchar();ll f=1,x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();                //输入挂模板
    return x*f;
}


int main()
{
    int t=read();
    while(t--) {
        unordered_map<int,int> mp;
        int n=read();
        for(int i=0; i<n; i++) {
            a[i]=read();
        }
        int ans=0;
        for(int j=1; j+1 < n; j++) {
            mp[a[j-1]]++;
            for(int k=j+1; k<n; k++) {
                if(mp.count(2*a[j]-a[k])) ans+=mp[2*a[j]-a[k]];
            }
        }
        printf("%d\n",ans);
    }
}