今日学习记录
1. 3583. 统计特殊三元组
关键词：数组 哈希表
问题分析：
找到数组中 0<i<j<k,且nums[i]==nums[j]*2==nums[k]的数量
核心思路:
枚举
先预处理所有数字的出现次数,采取枚举中间的数的做法,同时记录左端数组中数字的出现次数,预处理的 map 就右边的数量,每次枚举时,左端数量增多,右边减少,ans += l*r;
一次遍历(枚举右,维护左)
思考,我们不仅可以枚举中间,我们可以枚举右边,要找到mp[x]和mp[x/2],当右端为 x 时,就是要加上前面所有的 x 的数量,但是怎么确定中间出现过 x/2,我们在每次遍历到 x/2 的时候加上 x 的次数就行了
**最终代码：
const int MOD = 1e9+7;
int specialTriplets(vector<int>& nums) {
int n =nums.size();
unordered_map<int,long long> cnt1,cnt2;
long long ans = 0;
for(int x:nums){
if((x%2)==0) ans = (ans+cnt1[x/2])%MOD;
cnt1[x] += cnt2[x*2];
cnt2[x]++;
}
return ans%MOD;
}学到的点：
- 枚举右维护左