c++ - 为两个序列中第一个匹配项的距离之和提出一个最优算法

Question

我有两个列表，比如 L1 和 L2，两个列表长度的(最小)总和。

例如:

89 145 42 20 4 16 37 58 89

20 4 16 37 58 89

输出:5

89 145 42 20 4 16 37 58 89

56 678 123 65467

输出:0

19 82 68 100 1

100 1

输出:5

谢谢，

PS:我选择的语言是 C 和 C++，因此是标签。

Answer 1

将较短的列表添加到散列(字典)键=数字，值=列表中第一个实例的索引

遍历另一个列表并尝试在散列中查找每个元素。进行匹配时，将索引加在一起(哈希值加上列表中的当前索引)

这在 O(n) 中运行

boost::unordered_map 或 stdex::hash_map 可用于散列