本文介绍一种时间复杂度接近 O(n) 的线性扫描算法，用于在长度 ≤ 10⁶ 的数组中准确统计所有满足 (a, b, b) 格式、且保持原始相对顺序（非连续但下标递增）的本质不同三元组数量。
本文介绍一种时间复杂度接近 o(n) 的线性扫描算法，用于在长度 ≤ 10⁶ 的数组中准确统计所有满足 (a, b, b) 格式、且保持原始相对顺序（非连续但下标递增）的**本质不同三元组**数量。
要解决该问题，关键在于理解题意中的两个核心约束：
- 三元组必须保持原始下标顺序：即存在下标 $ i
-
统计的是“distinct triplets”：即三元组 $(a, b, b)$ 作为值组合去重（而非位置组合），例如
(5,3,3)只计 1 次，即使有多个位置对 $(j,k)$ 满足arr[j]=arr[k]=3。
暴力 $O(n^3)$ 和错误的频次枚举（如仅依赖全局 Counter）均不可行：前者超时；后者忽略了顺序约束——例如 [3,5,3] 中无法形成 (5,3,3)，因为 5 在第一个 3 之后、第二个 3 之前，不满足 i<j> 且 <code>arr[i]=5, arr[j]=arr[k]=3。
✅ 正确思路是逆向扫描 + 前缀唯一值计数：
- 对每个可能的
b，我们只关心其最后两次出现的位置（记为j和k，其中j ）； - 因为只有以
j和k作为后两个元素，才能使左侧可选的a（即arr[i]，i ）尽可能多，同时保证 <code>a ≠ b； - 对于该
b，合法a的数量 =arr[0:j]中不等于b的不同数值个数。
为此，我们设计两遍扫描：
? 第一遍（正向）：构建 first_occurrence_map 记录每个值首次出现位置，并同步计算前缀唯一值数量数组 unique_value_counts，其中 unique_value_counts[i] 表示 arr[0:i]（左闭右开）中不同数值的总数。
? 第二遍（逆向）：从右往左遍历，用字典 ans_counts 跟踪每个 b 能贡献多少 (a,b,b)。当首次遇到某值 b 时标记；第二次遇到（即它是倒数第二次出现）时，利用 unique_value_counts[j] 得到 arr[0:j] 的不同值总数，并减去 b 是否已在此前出现（即 first_occurrence_map[b] ？），从而得到有效的 <code>a 的种类数。
以下是优化后的完整实现（含注释与边界处理）：
from collections import defaultdict
def count_triplets_abb(arr):
n = len(arr)
if n < 3:
return 0
# Step 1: Forward pass — record first occurrence & prefix unique count
first_occ = {}
unique_count = [0] * (n + 1) # unique_count[i] = # distinct in arr[0:i]
for i, x in enumerate(arr):
if x not in first_occ:
first_occ[x] = i
unique_count[i + 1] = len(first_occ)
# Step 2: Backward pass — find second-to-last occurrence of each b
last_seen = {} # value -> last index seen
ans_counts = defaultdict(int)
for i in range(n - 1, -1, -1):
x = arr[i]
if x not in last_seen:
# First time seeing x from right → it's the last occurrence
last_seen[x] = i
elif i < last_seen[x]:
# This is the second-to-last occurrence (j), last_seen[x] is k
j = i
# Count distinct values in arr[0:j] excluding x itself
total_unique_left = unique_count[j]
# Subtract 1 if x appears before j (i.e., contributes to uniqueness there)
subtract = 1 if first_occ[x] < j else 0
ans_counts[x] = total_unique_left - subtract
# Mark as processed; skip earlier occurrences of same x
last_seen[x] = -1 # sentinel to avoid reprocessing
return sum(ans_counts.values())
# Example usage:
# print(count_triplets_abb([5, 6, 7, 3, 3, 3])) # → 3⚠️ 注意事项：
- 该算法时间复杂度为 O(n)（两次线性扫描 + 哈希表操作均摊 O(1)），空间复杂度 O(n)，完美适配 $N \leq 10^6$；
-
unique_count数组避免了每次动态求解前缀不同值个数，是性能关键； - 使用
last_seen[x] = -1标记已处理的b，确保每个b最多被计数一次； - 若某值
b出现少于 2 次，则自动跳过，无需额外判断。
? 总结：本方案摒弃了“枚举 a 和 b”的二维思维，转而聚焦于 b 的关键位置特征，结合前缀统计与逆向定位，将问题降维至单次线性扫描可解。这是处理大规模有序子序列计数类问题的经典范式——位置驱动 + 前缀/后缀预处理。
