1. 题意

求给定数组中下标 $(i, j, k)$ 的对数，且满足

$i < j < k, 2 a [j] = a [i] = a [k]$

2. 题解

2.1 枚举中间

三个数枚举中间那个数，再存前缀和后缀个数。

class Solution {
public:int specialTriplets(vector<int>& nums) {unordered_map<int,int> left;unordered_map<int,int> right;for (int num: nums) {right[num]++;}int ans = 0;int MOD = 1e9 + 7;int sz = nums.size();for (int i = 0; i < sz ; ++i) {int v = nums[i];right[v]--;ans = ans + (int) ( (long long)left[2 * v] * right[ 2 * v] % MOD) ;ans %= MOD;left[v]++;}return ans;}
};

2.2 枚举右边，维护左边

我们用两个哈希表记录，哈希表 $s_1$ 记录值为 $v$ 的个数；
哈希表 $s_{12}$ 记录序列 $(2 v, v)$ 的个数。

我们从左往右遍历，对每个值 $v$ 且 $\mod 2== 0$ , 相应的三元组个数为 $s_{12}\{ v / 2\}$ ；

$s_{12}\{v\}$ 的值需要累加上 $s_1\{2v\}$ 。

$s_1\{v\}$ 累加。注意顺序不能变，因为可能出现 $0, 0, 0$ 这种情况。

class Solution {
public:int specialTriplets(vector<int>& nums) {unordered_map<int,int> s1;unordered_map<int,int> s12;int MOD = 1e9 + 7;long long ans = 0;int sz = nums.size();for (int i = 0; i < sz; ++i) {int v = nums[i];if ( v % 2 == 0) {ans = (ans + s12[ v / 2]) % MOD;}s12[ v ] = ( s1[ v * 2 ] + s12[ v ] ) % MOD;s1[ v ]++;}return ans;}
};

2.3 二分

第一次遍历直接记录每个数出现的位置；

再次遍历，对于位置 $\in [1,n-1]$ ，

查找值为 $2 a [j]$ 出现位置中第一个不小于 $j$ 的下标。

这样就可以算出 $a [j]$ 的左边和右 $2 a [j]$ 的个数

class Solution {
public:int specialTriplets(vector<int>& nums) {unordered_map<int, vector<int>> h;int n = nums.size();for ( int i = 0; i < n; ++i) {h[ nums[i] ].push_back( i );}int ans = 0;int MOD = 1e9+7;for (int i = 1; i < n - 1; ++i) {int tg = 2 * nums[ i ];auto it = std::lower_bound( h[tg].begin(), h[tg].end(), i);int ln = static_cast<int>( it - h[tg].begin());int rn = static_cast<int>( h[tg].end() - it);if (it != h[tg].end() && *it == i) rn--;ans = ans  + (long long) ln * rn % MOD;ans %= MOD;}return ans;}
};