如何设计低时间复杂度算法实现双列表元素对应索引查找？

传统实现的性能瓶颈 #

常规暴力实现的逻辑为：遍历列表1的每个元素，逐次扫描列表2查找匹配位置、返回对应索引。这种方法的时间复杂度为 O(NM)*（N为列表1长度，M为列表2长度），当两个列表规模较大时，会出现明显的性能衰减。

最优效率方案：线性时间哈希映射法 #

该方案的整体时间复杂度为 O(M + N)，是当前匹配需求下的效率上限，具体执行步骤：

• 预处理阶段：仅完整遍历一次列表2，构建哈希映射表。映射表的键为列表2中的元素值，值为该元素在列表2中对应的索引。可根据实际业务规则，灵活调整索引的存储逻辑：可以存元素第一次出现的索引、最后一次出现的索引，也可以存储元素所有匹配位置的索引列表。
• 查询阶段：遍历列表1的每个元素，直接从已经构建好的哈希映射表中读取对应的索引值，过程中无需反复扫描列表2。

匹配效果示例：
假设列表2为 [7, 9, 15, 3, 20]，预处理构建的哈希映射为 {7:0, 9:1, 15:2, 3:3, 20:4}
若列表1为 [15, 3, 7]，通过映射直接得到的匹配结果为 [2, 3, 0]，和需求示例的匹配规则完全一致。

不同场景的适配调整 #

• 若列表2无重复元素：直接使用原生哈希表（Python的dict、Java的HashMap）存储元素与索引的对应关系即可，整体内存开销为O(M)，无额外性能损耗。
• 若列表2存在重复元素：根据业务规则调整映射表的写入逻辑——如果需要返回元素在列表2中第一次出现的索引，遍历列表2构建映射时，仅在键不存在时写入索引，遇到重复键直接跳过即可；如果需要返回所有匹配的索引列表，则将每个键对应的value维护为索引数组。
• 若内存资源极度受限：可选择先将列表2按元素值排序，同时保留元素对应的原始索引，之后对列表1的每个元素通过二分查找定位匹配位置。该方案整体时间复杂度为O(M log M + N log M)，性能略低于哈希表方案，但内存开销更低，适合列表2规模极大、哈希表内存占用超出阈值的极端场景。

常见性能反模式提醒 #

不要直接在批量匹配逻辑中调用列表的index()方法逐次查找元素，该方法每次调用都会从头扫描整个列表定位元素，本质和暴力遍历没有区别，数据量超过1k级就会出现明显的速度衰减。

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