如何比较两个不同数组的连续元素，提取匹配的连续值序列

核心思路 #

我们要找的是两个数组中同时出现且顺序完全连续的公共序列，最优实现的时间复杂度为O(n+m)预处理 + O(n)遍历，整体效率远高于暴力匹配：

• 先构建第二个数组的元素到索引的映射，O(m)时间复杂度，用来O(1)判断元素是否存在以及获取位置
• 遍历第一个数组，动态维护当前正在匹配的连续序列，判断当前元素和上一个匹配元素在第二个数组中是否是连续递增的位置关系，符合则继续累加，不符合则把已有的符合长度要求的序列存入结果
• 遍历结束后额外检查一次末尾剩余的序列，避免遗漏

代码实现（JavaScript） #

function getContinuousCommonSubarrays(arr1, arr2) {
  // 构建arr2的值到索引的映射表
  const arr2IndexMap = new Map(arr2.map((item, index) => [item, index]));
  const res = [];
  let currentMatch = [];
  let prevArr2Index = -2; // 初始值设为-2，保证首个匹配元素能正常初始化序列

  for (const item of arr1) {
    const currArr2Index = arr2IndexMap.get(item);
    // 元素存在且和上一个匹配元素在arr2中位置连续
    if (currArr2Index !== undefined && currArr2Index === prevArr2Index + 1) {
      currentMatch.push(item);
      prevArr2Index = currArr2Index;
    } else {
      // 存储符合长度要求的序列
      if (currentMatch.length >= 2) {
        res.push([...currentMatch]);
      }
      // 重置当前匹配序列
      currentMatch = currArr2Index !== undefined ? [item] : [];
      prevArr2Index = currArr2Index ?? -2;
    }
  }

  // 处理遍历结束后剩余的匹配序列
  if (currentMatch.length >= 2) {
    res.push([...currentMatch]);
  }

  return res;
}

// 测试用例
const array1 = ['1a', '4a', '3h', '78h', '5b', '6b', '7h'];
const array2 = ['3h', '1a', '4a', '5b', '6b', '7h'];
console.log(getContinuousCommonSubarrays(array1, array2)); // 输出 [['1a','4a'], ['5b','6b','7h']]

补充说明 #

如果你的数组规模极大，还可以提前做一次交集过滤，把仅在单个数组中出现的元素先筛掉，减少后续遍历的无效计算，进一步提升效率。

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