LeetCode 两个数组的交集 JavaScript Set 题解

题目

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是 唯一的。我们可以不考虑输出结果的顺序 。

解题思路

题目有两个约束决定了解法：结果元素必须唯一，顺序不限。

「唯一」意味着要去重，「顺序不限」意味着不用保持原数组的相对位置，可以放心用哈希结构。

暴力解法是两层循环互相比对，再对结果去重，那是 O(m * n)。优化点还是查找：内层循环本质是在问「这个元素在另一个数组里存在吗」，把其中一个数组转成集合，查找就从 O(n) 变成 O(1)，整体降到 O(m + n)。

去重和查找这两个需求，Set 一个结构就都满足了——它天然不存重复值，has 又是常数时间。所以这道题是 Set 最典型的应用场景。

题解

使用集合

这一版思路很直接：nums1 转成 Set 再摊回数组，完成去重；nums2 转成 Set，用来做快速查找。然后过滤一遍留下两边都有的。

var intersection = function (nums1, nums2) {
  const n1 = [...new Set(nums1)];
  const n2 = new Set(nums2);

  return n1.filter(item => {
    return n2.has(item);
  });
};

intersection([1, 2, 2, 1], [2, 2]);

两个 Set 的用途不同，这一点值得分清：n1 用完 Set 就摊成数组了，只是借它去重，因为后面要用数组的 filter；n2 保持 Set 形态，因为需要的是它的 has 查找能力。

去重必须在 nums1 这边做。假设不去重，[1, 2, 2, 1] 和 [2, 2] 求交集，filter 会保留两个 2，结果里出现重复，不满足题目要求。而 nums2 那边不需要显式去重——它只用来判断存在性，重复值对 has 的结果没有影响，new Set 顺手也去掉了。

Set 的判重用的是同值零算法，跟 === 基本一致，对本题的整数场景没有区别。要注意的是它按值比较原始类型、按引用比较对象，所以这个解法只适用于原始类型的数组，如果数组里装的是对象，has 判断的是同一个引用而不是内容相同。

时间复杂度是 O(m + n)，两个数组各遍历一次，查找是常数时间。空间是 O(m + n)，两个 Set 各存一份。

使用字典

第二个版本换成 Map，多做了一件事——查到之后把键删掉。

var intersection = function (nums1, nums2) {
  const map = new Map();
  nums1.forEach(n => {
    map.set(n, true);
  });

  const res = [];

  nums2.forEach(n => {
    if (map.get(n)) {
      res.push(n);
      map.delete(n);
    }
  });

  return res;
};

map.delete(n) 是这一版的关键，它承担了去重的职责。

思路上有个转变：上一版是先把 nums1 去重再过滤，这一版不预先去重，而是靠「用过就删」保证每个值最多进结果一次。遍历 nums2 时如果某个值出现两次，第一次命中会 push 并删除映射，第二次再查就查不到了，自然跳过。

这么写省掉了一次去重遍历，只需要把 nums1 建成映射、nums2 走一遍，结构上比上一版更紧凑。

两个小点。一是这里的值存的是 true，其实只用到了键，用 Set 语义上更贴切，Map 在这里的价值只是提供了 delete——但 Set 也有 delete，所以这道题用 Set 加 delete 是更自然的写法。二是判断条件写的是 if (map.get(n))，依赖值为真值，如果哪天把存的值改成 0 或者空字符串，这个判断就失效了，用 map.has(n) 更稳妥。

复杂度和上一版相同，时间 O(m + n)，空间 O(m)——只存了 nums1 的映射，比上一版省一点。

顺带说，如果题目改成要求结果保留重复元素的出现次数（也就是「两个数组的交集 II」那道），就不能用 Set 了，得用 Map 记录每个值出现的次数，命中时把计数减一而不是直接删除。