Pengjielee's blog

题目

给定两个数组，编写一个函数来计算它们的交集。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。

进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

1、哈希表

由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。

首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

JS实现

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
  const len1 = nums1.length;
  const len2 = nums2.length;
  if (len1 === 0 || len2 === 0) {
    return [];
  }
  const result = [];

  const map = new Map();
  // 遍历较短的数组，把【数字->出现次数】存进哈希表
  let nums = len1 < len2 ? nums1 : nums2;
  for (let i = 0; i < nums.length; i++) {
    const key = nums[i];
    //如果不存在，设置默认值为0
    if (!map.has(key)) {
      map.set(key, 0);
    }
    //次数+1
    const count = map.get(key) + 1;
    //更新次数
    map.set(key, count);
  }

  // 遍历较长的数组
  nums = len2 > len1 ? nums2 : nums1;
  for (let i = 0; i < nums.length; i++) {
    const key = nums[i];
    //获取次数
    let count = map.get(key);
    //如果存在，则添加到结果集
    if (count > 0) {
      result.push(key);
      count--;
      // ？怎么又判断一次
      if (count > 0) {
        map.set(key, count);
      } else {
        map.delete(key);
      }
    }
  }
  return result;
};