leetcode_3583 统计特殊三元组

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