如何在JavaScript中计算两个数组的差异（包含元素移动的情况）

核心思路 #

整体分三步处理，彻底避免把元素新增/删除导致的整体索引偏移误判为移动：

• 第一步：先筛选出新增元素（仅在新数组存在）和删除元素（仅在旧数组存在）
• 第二步：提取两个数组的公共元素序列，把新增、删除元素过滤后，剩余元素按原本的先后顺序保留
• 第三步：用最长公共子序列（LCS）算法找出公共序列中相对位置没有发生变化的元素，剩余的公共元素就是发生了相对位置移动的元素

实现代码 #

function diffArrays(oldArr, newArr) {
  // 第一步：筛选新增、删除的元素
  const oldSet = new Set(oldArr);
  const newSet = new Set(newArr);
  
  const added = newArr.filter(item => !oldSet.has(item));
  const removed = oldArr.filter(item => !newSet.has(item));

  // 第二步：提取公共元素的原始顺序序列
  const oldCommon = oldArr.filter(item => newSet.has(item));
  const newCommon = newArr.filter(item => oldSet.has(item));

  // 第三步：通过最长公共子序列标记未移动元素，筛选移动元素
  const lcs = getLCS(oldCommon, newCommon);
  const lcsSet = new Set(lcs);
  const moved = [...new Set([...oldCommon, ...newCommon].filter(item => !lcsSet.has(item)))];

  return { added, removed, moved };
}

// 辅助函数：计算两个数组的最长公共子序列
function getLCS(arr1, arr2) {
  const m = arr1.length;
  const n = arr2.length;
  const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));

  // 填充动态规划表
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (arr1[i - 1] === arr2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  // 回溯获取最长公共子序列
  let i = m, j = n;
  const lcs = [];
  while (i > 0 && j > 0) {
    if (arr1[i - 1] === arr2[j - 1]) {
      lcs.unshift(arr1[i - 1]);
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  return lcs;
}

// 测试用例
let old = [ "b", "c", "d", "e", "f", "g", "h", "i", "j" ];
let news = [ "a", "d", "c", "e", "f", "h", "i", "j" ];
console.log(diffArrays(old, news));
// 输出结果和需求完全一致：
// added: ["a"], removed: ["b", "g"], moved: ["d", "c"]

注意事项 #

如果数组中存在重复元素，只需要把上述代码的集合判断逻辑，替换为基于元素唯一标识的判断即可，比如给每个元素附加唯一id，按id判断是否为同一个元素。

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