JavaScript中如何计算包含重复值的两个数组的差值

我们需要判断一个数组是否被另一个数组包含，并返回前者中缺失的元素，且需要兼容数组存在重复值的场景，具体效果符合以下示例：

getDiff([1, 2, 3], [1, 2, 3, 4]) --> []

getDiff([1, 2, 2, 3], [1, 2, 3, 4]) --> [2]

getDiff(["A", "B", "C"], ["B", "B", "A", "C"]) --> []

getDiff(["B", "B", "B"], [3, 2, 1]) --> ["B", "B", "B"]

实现思路 #

• 统计第二个数组中所有元素的出现频次，存储为哈希映射结构
• 遍历第一个数组的每一个元素：若当前元素在哈希映射中还有剩余计数，则扣除1次计数；若没有剩余计数，则将该元素加入缺失结果数组
• 最终返回的缺失数组就是前者中未被后者包含的元素

代码实现 #

function getDiff(sourceArr, targetArr) {
  // 统计目标数组的元素出现频次
  const freqMap = {};
  for (const item of targetArr) {
    freqMap[item] = (freqMap[item] || 0) + 1;
  }

  const missingItems = [];
  // 遍历源数组匹配频次
  for (const item of sourceArr) {
    if (freqMap[item] > 0) {
      freqMap[item]--;
    } else {
      missingItems.push(item);
    }
  }

  return missingItems;
}

注意事项 #

• 该实现时间复杂度为O(n+m)，其中n和m分别是两个数组的长度，性能优于嵌套遍历的暴力方案
• 仅支持基础类型（数字、字符串、布尔值、null、undefined）的直接匹配，若需要支持引用类型（对象、数组）的匹配，可自行修改哈希映射的key生成逻辑，比如将元素序列化后作为key

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