# 超时
“`C++
class Solution {
public:
int specialTriplets(vector
int n = nums.size();
long long ans = 0;
const int MOD = 1e9 + 7;
unordered_map
for (int i = 0; i < n; i++)
{
cnt[nums[i]]++;
}
for (int k = 1; k < n - 1; k++)
{
int b = nums[k];
int num_a = 0;
int num_c = 0;
for (int i = 0; i < k; i++)
{
if (nums[i] == b * 2) num_a++;
}
num_c = cnt[b * 2] - num_a;
if (b == 0) num_c--;
ans = (ans + (num_a * num_c) % MOD) % MOD;
}
return ans;
}
};
```
# 答案
```C++
class Solution {
public:
int specialTriplets(vector
constexpr int MOD = 1e9 + 7;
unordered_map
for (auto x : nums)
{
suf[x]++;
}
long long ans = 0;
unordered_map
for (int x : nums)
{
suf[x]–;
ans += 1LL * pre[x * 2] * suf[x * 2];
pre[x]++;
}
return ans % MOD;
}
};
“`
### 1. 核心差异：时间复杂度
这是导致“超时”的根本原因。
– **超时代码 (TLE)**：
– **复杂度**：$O(N^2)$。
– **原因**：外层循环枚举中间点 `k`，内层循环 `for (int i = 0; i < k; i++)` 每次都要重新扫描一遍左边的数组来统计 `num_a`。当 $N=10^5$ 时，计算量达到 $10^{10}$ 级别，远超通常的 $10^8$ 限制。
- **答案代码 (AC)**：
- **复杂度**：$O(N)$。
- **原因**：去掉了内层循环。利用**哈希表（或数组）实时维护**前缀信息。每移动一步，只需要 $O(1)$ 的时间更新 `pre` 和 `suf`，不需要回头重新扫描。
------
### 2. 优化逻辑：由“静态统计”转向“动态维护”
做笔记时，重点记录这个思维转变过程：
- **暴力思维 (TLE)**：
- “我现在到了第 `k` 个位置，我不记得前面发生了什么，所以我得回头**重新数一遍**前面有多少个符合条件的数。”
- **优化思维 (AC)**：
- “我一路走过来，用一个小本子 (`pre` map) **随手记下**刚才见过的数字。当我走到第 `k` 个位置时，不用回头，直接查小本子就知道前面有多少个符合条件的数。”
------
### 3. 代码实现细节对比 (笔记重点)
请在笔记中着重标注 **AC 代码** 的这三个步骤，这是处理“三元组问题”的标准操作流：
#### A. 预处理 (Pre-processing)
先把所有元素放入“右侧池子” (`suf`)。
```C++
// 初始化：假设指针在最左边，所有元素都在右边 (suffix)
for (auto x : nums) suf[x]++;
```
#### B. 核心循环三部曲 (The 3-Step Loop)
这是优化的精髓，顺序绝对不能乱：
1. **移出右侧**：当前遍历到的元素 `x` 也就是中间元素 `nums[j]`，它不再属于“未来”了，所以从 `suf` 中减去。
2. **计算贡献**：利用当前的 `pre` (左侧历史) 和 `suf` (右侧剩余) 直接计算答案。
3. **加入左侧**：当前元素 `x` 处理完毕，对于下一个元素来说，`x` 变成了“历史”，所以加入 `pre`。
```C++
for (int x : nums) {
// 1. 现任变前任：它不再是右边的元素了
suf[x]--;
// 2. 搞事情：左边有多少个目标 * 右边有多少个目标
// 这里的 x 就是中间那个数，我们要找的是左右两边等于 x*2 的数
ans += 1LL * pre[x * 2] * suf[x * 2];
// 3. 记录历史：把它加入左边的记录，供后面的人查询
pre[x]++;
}
```
------
### 4. 笔记总结模板 (Copy 此处)
> **【算法笔记】三元组问题 ($i < j < k$) 通用解法**
>
> **场景**：在数组中寻找满足特定数值关系的三元组 (如 `nums[i] == a, nums[j] == b, nums[k] == c`)。
>
> **核心技巧**：**枚举中间元素 `j`**。
>
> – 固定中间元素 `j`，问题转化为：“在 `j` 左边找有多少个 `a`，在 `j` 右边找有多少个 `c`”。
> – 答案 = $\sum (\text{count\_left}[a] \times \text{count\_right}[c])$。
>
> **数据结构**：
>
> – `pre` Map/Array：维护 `0` 到 `j-1` 的频率（动态增加）。
> – `suf` Map/Array：维护 `j+1` 到 `n-1` 的频率（动态减少）。
>
> **防坑点**：
>
> 1. **初始化**：`suf` 先填满，`pre` 为空。
> 2. **更新顺序**：先 `suf[x]–` (当前元素移出右边)，再计算 `ans`，最后 `pre[x]++` (当前元素加入左边)。
> 3. **数据溢出**：乘积可能超过 `int`，累加 `ans` 时必须强转 `long long` (即 `1LL * …`)。
### 5. 额外提示 (Corner Case)
在你的 TLE 代码中，有一行处理非常棘手：
“`C++
if (b == 0) num_c–;
“`
这是因为在暴力法中，你是用 `总数 – 左边 = 右边` 来算右边的。如果目标数是 0，且当前中间数也是 0，`2*b` 还是 0，你会把**当前这个 0** 也算进右边去，所以要减掉。
**AC 代码的优势**：通过 `suf[x]–` 在计算前就把当前元素移除了，**天然避免了**这个问题，不需要特殊判断 0 的情况，代码更简洁、不易出错。