前置知识

查找表是一种存储结构，专门用来存储无逻辑关系的数据。也就是说，查找表就是一个包含众多元素的集合，表中的各个元素独立存在，之间没有任何关系。通过查找表，我们可以更为快速地去查询数据。
在数据结构中，将存储无逻辑关系数据的线性表、树或者图结构统称为查找表。

例题

350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。 :::info 示例 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 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办

    思路

    为两个数组分别建立 map，统计每个数字出现的数量。
    然后对其中一个 map 进行遍历，查看这个数字在两个数组中分别出现的数量，取出现的最小的那个数量，push 到结果数组中即可。

    1. var intersect = function(nums1, nums2) {
    2.   const map1 = new Map();
    3.   const map2 = new Map();
    4.   for (let item of nums1) {
    5.       map1.set(item, (map1.get(item) || 0) + 1)
    6.   }
    7.   for (let item of nums2) {
    8.       map2.set(item, (map2.get(item) || 0) + 1);
    9.   }
    10.   const res = [];
    11.   for (let key of map1.keys()) {
    12.       const count1 = map1.get(key);
    13.       const count2 = map2.get(key);
    14.       if (count2) {
    15.           const pushCount = Math.min(count1, count2);
    16.           for (let i = 0; i < pushCount; i++) {
    17.               res.push(key);
    18.           }
    19.       }
    20.   }
    21.   return res;
    22. };

    进阶

  • 当数组已经排好序时，我们可以采用 双指针 的方法解决。

  • 当 nums2 容量过大时，我们可以优先遍历容量大的数组，提前结束循环。