注意这里的三元组是按顺序找出来的,不能够随便组合。
由于数组长度不算很大,我们可以实现一层循环。
根据题目,我们分别调取对于当前遍历到的三元组,第一个数不同其余数相同,第二个数不同其余数相同,第三个数相同其余数不同,所有数都相同的数量,然后加上前三个减去最后一个的三倍,具体原因见下图集合关系。
在算完当前这一层循环之后,我们更新下这些情况下的数量,供之后的三运组进行运算。
CODE:
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long longvoid solve(){int n;cin >> n;vector<int>a(n+1);for(int i = 1;i <= n;i++)cin >> a[i];map<pii,int>m1;map<pii,int>m2;map<pii,int>m3;map<pair<pii,int>,int>m4;long long res = 0;for(int i = 1;i <= n-2;i++){res = res + (m1[{a[i],a[i+1]}] + m2[{a[i],a[i+2]}] + m3[{a[i+1],a[i+2]}] - (ll)3*m4[{{a[i],a[i+1]},a[i+2]}]);m1[{a[i],a[i+1]}] ++;m2[{a[i],a[i+2]}]++;m3[{a[i+1],a[i+2]}]++;m4[{{a[i],a[i+1]},a[i+2]}]++;}cout << res << endl;
}int main(){int T;cin >> T;while(T--){solve();} return 0;
}