本文介绍一种基于元素频次特征（每个键最多对应 0/1/2 个相同值）的 o(n) 线性时间解法，通过哈希表一次遍历实现唯一值提取，避免嵌套查找，显著提升 2000+ 数据量下的性能。
本文介绍一种基于元素频次特征（每个键最多对应 0/1/2 个相同值）的 o(n) 线性时间解法，通过哈希表一次遍历实现唯一值提取，避免嵌套查找，显著提升 2000+ 数据量下的性能。
在实际开发中，我们常需从主键列表 A 和其关联值列表 B（以映射形式存在）中识别“真正唯一”的键——即该键在 B 中未出现（空列表）、或仅出现一次且等于自身（如 [10010]），但不包括重复出现两次及以上（如 [10020, 10020]）或完全不匹配（如 [10021]）的情况。原始代码使用 B.contains(val) 在内层循环中线性查找，导致整体时间复杂度为 O(n²)，当 A 规模达 2000+ 时性能急剧下降。
关键突破口在于题目隐含约束：每个 A 中的元素 val 对应的 B 列表长度 ≤ 2，且所有元素均来自 A 或为空。这意味着我们只需统计每个 val 在所有 B 列表中作为有效值出现的总次数：
- 出现 0 次 → 唯一（如
10010 = []）✅ - 出现 1 次且值等于
val→ 唯一（如10010 = [10010]）✅ - 出现 2 次且均为
val→ 非唯一（如10020 = [10020, 10020]）❌ - 出现 1 次但值 ≠
val→ 非唯一（违反题设，可忽略）
因此，最优解法是：单次遍历所有 B 列表，用 HashMap 统计每个值的出现频次；再遍历 A，筛选出频次为 0 的元素。该方案时间复杂度稳定为 O(n + m)（n = |A|, m = 所有 B 列表元素总数 ≤ 2n），空间复杂度 O(n)，真正实现线性可扩展。
以下是 Kotlin 实现示例：
fun findUniqueKeys(A: List<int>, BMap: Map<int list>>): List<int> {
// 步骤1：统计所有 B 值的出现频次（一次遍历）
val freq = mutableMapOf<int int>()
for (bList in BMap.values) {
for (bVal in bList) {
freq[bVal] = freq.getOrDefault(bVal, 0) + 1
}
}
// 步骤2：遍历 A，收集在 B 中未出现的 key
return A.filter { !freq.containsKey(it) }
}
// 调用示例
val A = listOf(10010, 10020, 99948)
val BMap = mapOf(
10010 to emptyList(),
10020 to listOf(10020, 10020),
99948 to listOf(99948, 99948)
)
val result = findUniqueKeys(A, BMap) // 输出: [10010]</int></int></int></int>
⚠️ 注意事项：
- 若
B的结构非Map<int list>></int>而是List<list>></list>且与A严格位置对应（即A[i]对应B[i]），可直接索引访问，无需哈希映射，进一步减少开销； - 本解法假设
B中所有非空元素均属于A（题设保证），故无需额外校验； - 使用
HashMap而非ArrayList.contains()是性能跃升的核心——将内层 O(k) 查找降为 O(1) 平均访问； - 对于超大规模数据（如百万级），可考虑
IntOpenHashSet（Kotlin/kotlinx-collections）替代HashMap以降低内存占用。
总结：利用题设的频次上限特性，将问题转化为「频次统计 + 零频筛选」，以空间换时间，彻底规避嵌套循环，在保持代码简洁的同时达成理论最优复杂度。
