350. 两个数组的交集 II

方法一：使用 Map 数据结构

先将 nums1 通过 Map 来记录每个数字出现的次数，然后对 num2 进行遍历。如果数字在 map 中，则对 map 中的次数减一，如果出现次数变为 0，则将数字从 map 中去除。

var intersect = function(nums1, nums2) {
  if (nums1.length > nums2) {
    [nums1, nums2] = [nums2, nums1]
  }
  const map1 = new Map();
  nums1.forEach(num => {
    map1.set(num, map1.get(num) ? map1.get(num) + 1 : 1)
  })
  const result = []
  nums2.forEach(num => {
    if (map1.get(num)) {
      result.push(num)
      map1.set(num, map1.get(num) - 1)
            // 当该数字次数变为 0 的时候，将该数字从 Map 中清除
      if (map1.get(num) === 0) {
        map1.delete(num)
      }
    }
  })
  return result
};

• 时间复杂度
• 空间复杂度为

方法二：使用双指针

如果数组时有序的，则可以使用双指针来求交集。该解法与 349 的双指针解法相同，却别在于 349 结果需要去重，而该题是不需要去重的。

var intersect = function(nums1, nums2) {
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  const length1 = nums1.length, length2 = nums2.length;
  let index1 = 0, index2 = 0;
  const result = []
  while(index1 < length1 && index2 < length2) {
    const num1 = nums1[index1]
    const num2 = nums2[index2]
    if (num1 === num2) {
      result.push(num1)
      index1++;
      index2++;
    } else if (nums1[index1] > nums2[index2]) {
      index2++;
    } else {
      index1++;
    }
  }
  return result;
};

• 时间复杂度
• 空间复杂度

进阶问题

第一个问题：如果数组已经排好序，则可以使用双指针的方式进行求解，也就是前面的方法二，它的时间复杂度级别是 级别的。

第二个问题：

第三个问题：由于 nums2 较大，无法一次加载所有元素到内存中，因此就没法高效地对 nums2 进行排序，因此应使用方法一。