方法一：枚举中间
三变量问题，一般枚举中间的变量最简单。为什么？对比一下：
- 枚举 $i$，后续计算中还需保证 $j < k$。
- 枚举 $j$，那么 $i$ 和 $k$ 自动被 $j$ 隔开，互相独立，后续计算中无需关心 $i$ 和 $k$ 的位置关系。
枚举中间的 $j$，问题变成：
- 在 $[0,j-1]$ 中，$\textit{nums}[j]\cdot 2$ 的出现次数。
- 在 $[j+1,n-1]$ 中，$\textit{nums}[j]\cdot 2$ 的出现次数。
- 在这些出现次数中，左右两边各选一个。根据乘法原理，把这两个出现次数相乘，加到答案中。
用哈希表（或者数组）统计 $j$ 左右每个数的出现次数。
- 右边的元素出现次数，可以先统计整个数组，然后再次遍历数组，撤销 $[0,j]$ 中统计的元素出现次数，即为 $[j+1,n-1]$ 中的元素出现次数。
- 左边的元素出现次数，可以一边遍历 $\textit{nums}$，一边统计。
由于答案不超过 $n\cdot 10^5\cdot 10^5 \le 10^{15}$，可以只在返回时取模。
本题视频讲解，欢迎点赞关注~
###py
class Solution:
def specialTriplets(self, nums: List[int]) -> int:
MOD = 1_000_000_007
suf = Counter(nums)
ans = 0
pre = defaultdict(int) # 比 Counter 快
for x in nums: # x = nums[j]
suf[x] -= 1 # 撤销
# 现在 pre 中的是 [0,j-1]，suf 中的是 [j+1,n-1]
ans += pre[x * 2] * suf[x * 2]
pre[x] += 1
return ans % MOD
###java
// 更快的写法见【Java 数组】
class Solution {
public int specialTriplets(int[] nums) {
final int MOD = 1_000_000_007;
Map<Integer, Integer> suf = new HashMap<>();
for (int x : nums) {
suf.merge(x, 1, Integer::sum); // suf[x]++
}
long ans = 0;
Map<Integer, Integer> pre = new HashMap<>();
for (int x : nums) { // x = nums[j]
suf.merge(x, -1, Integer::sum); // suf[x]-- // 撤销
// 现在 pre 中的是 [0,j-1]，suf 中的是 [j+1,n-1]
ans += (long) pre.getOrDefault(x * 2, 0) * suf.getOrDefault(x * 2, 0);
pre.merge(x, 1, Integer::sum); // pre[x]++
}
return (int) (ans % MOD);
}
}
###java
class Solution {
public int specialTriplets(int[] nums) {
final int MOD = 1_000_000_007;
int mx = 0;
for (int x : nums) {
mx = Math.max(mx, x);
}
int[] suf = new int[mx + 1];
for (int x : nums) {
suf[x]++;
}
long ans = 0;
int[] pre = new int[mx + 1];
for (int x : nums) {
suf[x]--;
if (x * 2 <= mx) {
ans += (long) pre[x * 2] * suf[x * 2];
}
pre[x]++;
}
return (int) (ans % MOD);
}
}
###cpp
class Solution {
public:
int specialTriplets(vector<int>& nums) {
const int MOD = 1'000'000'007;
unordered_map<int, int> suf;
for (int x : nums) {
suf[x]++;
}
long long ans = 0;
unordered_map<int, int> pre;
for (int x : nums) { // x = nums[j]
suf[x]--; // 撤销
// 现在 pre 中的是 [0,j-1]，suf 中的是 [j+1,n-1]
ans += 1LL * pre[x * 2] * suf[x * 2];
pre[x]++;
}
return ans % MOD;
}
};
###go
func specialTriplets(nums []int) (ans int) {
const mod = 1_000_000_007
suf := map[int]int{}
for _, x := range nums {
suf[x]++
}
pre := map[int]int{}
for _, x := range nums { // x = nums[j]
suf[x]-- // 撤销
// 现在 pre 中的是 [0,j-1]，suf 中的是 [j+1,n-1]
ans += pre[x*2] * suf[x*2]
pre[x]++
}
return ans % mod
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
- 空间复杂度：$\mathcal{O}(n)$。
方法二：枚举右，维护左（一次遍历）
枚举 $k$，设 $x=\textit{nums}[k]$，问题变成：
- 有多少个二元组 $(i,j)$，满足 $i<j<k$ 且 $\textit{nums}[i]=x$ 且 $\textit{nums}[j] = \dfrac{x}{2}$。用哈希表 $\textit{cnt}_{12}$ 记录这样的二元组个数。
这个问题也可以枚举右维护左，即枚举 $j$，问题变成：
- 在 $j$ 左边有多少个数等于 $\textit{nums}[j]\cdot 2$？用哈希表 $\textit{cnt}_{1}$ 记录。
###py
class Solution:
def specialTriplets(self, nums: List[int]) -> int:
MOD = 1_000_000_007
cnt1 = defaultdict(int)
cnt12 = defaultdict(int)
cnt123 = 0
for x in nums:
if x % 2 == 0:
cnt123 += cnt12[x // 2] # 把 x 当作 nums[k]
cnt12[x] += cnt1[x * 2] # 把 x 当作 nums[j]
cnt1[x] += 1 # 把 x 当作 nums[i]
return cnt123 % MOD
###java
class Solution {
public int specialTriplets(int[] nums) {
final int MOD = 1_000_000_007;
Map<Integer, Integer> cnt1 = new HashMap<>();
Map<Integer, Long> cnt12 = new HashMap<>();
long cnt123 = 0;
for (int x : nums) {
if (x % 2 == 0) {
cnt123 += cnt12.getOrDefault(x / 2, 0L); // 把 x 当作 nums[k]
}
cnt12.merge(x, (long) cnt1.getOrDefault(x * 2, 0), Long::sum); // 把 x 当作 nums[j]
cnt1.merge(x, 1, Integer::sum); // 把 x 当作 nums[i]
}
return (int) (cnt123 % MOD);
}
}
###cpp
class Solution {
public:
int specialTriplets(vector<int>& nums) {
const int MOD = 1'000'000'007;
unordered_map<int, int> cnt1;
unordered_map<int, long long> cnt12;
long long cnt123 = 0;
for (int x : nums) {
if (x % 2 == 0) {
cnt123 += cnt12[x / 2]; // 把 x 当作 nums[k]
}
cnt12[x] += cnt1[x * 2]; // 把 x 当作 nums[j]
cnt1[x]++; // 把 x 当作 nums[i]
}
return cnt123 % MOD;
}
};
###go
func specialTriplets(nums []int) (cnt123 int) {
const mod = 1_000_000_007
cnt1 := map[int]int{}
cnt12 := map[int]int{}
for _, x := range nums {
if x%2 == 0 {
cnt123 += cnt12[x/2] // 把 x 当作 nums[k]
}
cnt12[x] += cnt1[x*2] // 把 x 当作 nums[j]
cnt1[x]++ // 把 x 当作 nums[i]
}
return cnt123 % mod
}
复杂度分析
- 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
- 空间复杂度：$\mathcal{O}(n)$。
相似题目
更多相似题目，见下面数据结构题单的「§0.2 枚举中间」和动态规划题单的「专题：前后缀分解」。
分类题单
如何科学刷题？
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
我的题解精选（已分类）
登录