350. 两个数组的交集 II

题目

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

例

输入: nums1 = [1,2,2,1], nums2 = [2,2]

输出: [2,2]

说明：

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

进阶:

如果给定的数组已经排好序呢？你将如何优化你的算法？

如果  nums1  的大小比  nums2  小很多，哪种方法更优？

如果  nums2  的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加 载所有的元素到内存中，你该怎么办？

题解

哈希表

先遍历数组 1，用哈希表存储数字和对应出现的次数，然后再遍历数组 2，如果出现过就加入结果数组，哈希表次数减一

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
  let m = new Map();
  for (let i = 0; i < nums1.length; ++i) {
    const cur = nums1[i];
    if (!m.has(cur)) {
      m.set(cur, 1);
    } else {
      m.set(cur, m.get(cur) + 1);
    }
  }
  let ans = [];
  for (let j = 0; j < nums2.length; ++j) {
    const cur = nums2[j];
    if (m.get(cur)) {
      m.set(cur, m.get(cur) - 1);
      ans.push(cur);
    }
  }
  return ans;
};

排序 + 双指针

排序后用两个指针分别指向两个数组，相同就都往后移，不同就移动较小的指针，遍历完其中一个就返回结果

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
  // 排序
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  // 双指针
  let i = (j = 0);
  let ans = [];
  while (i < nums1.length && j < nums2.length) {
    const a = nums1[i];
    const b = nums2[j];
    if (a === b) {
      ans.push(a);
      i++;
      j++;
    } else {
      if (a > b) j++;
      else i++;
    }
  }
  return ans;
};