1. 題意

求給定數組中下標$(i,j,k)$的對數， 且滿足

$$i<j<k,2a[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}$記錄序列$(2v,v)$的個數。

我們從左往右遍歷，對每個值$v$且$v\mathrm{mod}2==0$, 相應的三元組個數為 s 12 { v / 2 } s_{12}\{ v / 2\} s12?{v/2}；

s 12 { v } s_{12}\{v\} s12?{v}的值需要累加上 s 1 { 2 v } s_1\{2v\} s1?{2v}。

s 1 { v } s_1\{v\} s1?{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 二分

第一次遍歷直接記錄每個數出現的位置；

再次遍歷，對于位置$j\in [1,n?1]$，

查找值為$2a[j]$出現位置中第一個不小于$j$的下標。

這樣就可以算出$a[j]$的左邊和右$2a[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;}
};

3. 參考

03xf