高效判断二维数组D子数组在A/B/C数组中归属的实现方法

你现在方案慢的核心原因是嵌套循环的时间复杂度太高：每个D里的三元组最坏要遍历3000次A/B/C元素做比较，总比较次数接近1.7亿次，耗时必然很长。最快的方案是用哈希表做预处理，把单次匹配的时间复杂度从O(n)压到O(1)，整体性能比暴力循环快3个数量级，完全适配你的场景。

具体实现步骤 #

• 预处理构建哈希映射表
  因为A、B、C里的三元组全局唯一，不需要处理键冲突，直接遍历A、B、C三个数组的所有三元组，把三元组作为键，对应的所属数组标记（比如用整数0代表A、1代表B、2代表C）作为值，全部存入同一个哈希表（字典/散列结构）即可。

  提速技巧：如果三元组里每个整数的取值不超过2097152（2^21），可以直接把三个int编码成一个64位长整数当哈希键，比用元组、数组、结构体当键的哈希计算速度快30%以上，编码逻辑参考：key = (long)a << 42 | (long)b << 21 | c，如果存在负数，先给每个值加固定偏移量转成无符号数再编码就行。
  不要分开建三个哈希表按A→B→C顺序查，建一个统一表一次查完最快，能省两次哈希查询的开销。

• 遍历D数组直接查表处理
  遍历D里的每个三元组，用和预处理时完全一致的规则生成键，直接去哈希表里查：
  • 查到标记0，执行A数组匹配对应的后续逻辑
  • 查到标记1，执行B数组匹配对应的后续逻辑
  • 查到标记2，执行C数组匹配对应的后续逻辑
  • 查不到就走无匹配的兜底逻辑
    整个过程完全不需要遍历A/B/C，单次查询平均耗时是常数级。

额外提速点（适配D有重复的场景） #

你提到D里的三元组存在重复，可以加个简单的结果缓存：第一次查到某个三元组的匹配结果后，把结果存在临时缓存里，后面再遇到相同的三元组直接取缓存结果，连哈希查表的开销都能省掉，D里重复率越高，这个优化的收益越大。

性能参考 #

• 原嵌套循环方案：总操作量约1.7亿次，普通消费级CPU单线程跑大概要1.5~2秒
• 哈希表方案：总操作量约6万次，算上哈希计算的开销，单线程跑耗时在1毫秒以内，性能差距上千倍

内容的提问来源于stack exchange，提问作者user12726266