两个数组的交集

题目

求两个数组的交集。（属于查找表问题）

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

示例：

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

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

思路

• 使用 Map 记录一个数组的每个元素出现的次数。比如 [1, 1, 2] 用 Map 记录表示就是 [[1, 2], [2, 1]]。其中 key 是数组元素，用 num 表示。value 是 num 出现次数，用 count 表示。
• 遍历其中一个 Map 的 key（Map.keys()），检查是否能在另一个 Map 中找到相同的 key。能找到就取这个 key 所代表的最小 count。然后将这个 key push 到一个最终会返回的数组中 count 次。
• 如果对返回结果有顺序要求，在返回最后结果之前，还得进行一次排序。否则可能是无序的。

注意点

• 注意使用 map 的 keys 方法获取 key 的数组。
• 注意在 for of 循环中，区分 return、break、continue 的作用

代码

function intersection (nums1: number[], nums2: number[]) {
  const map1 = makeMap(nums1)
  const map2 = makeMap(nums2)
  const resArr: number[] = []
  // 注意使用 map 的 keys 方法
  for(const key of map1.keys()) {
    // 如果找得到，推出至少存在一个，说明存在相同的 num
    if(map2.get(key)) {
      const count = Math.min(map1.get(key), map2.get(key))
      for(let i = 0; i < count; i++) {
        // key 对应的是 nums[number] 的数字元素
        resArr.push(key)
      }
    } else {
      // break 关键字会跳出循环。
      // 注意：return 会终止最外层函数执行，return 会直接返回 undefind ！！
      // 要想跳过这次循环，应该使用 continue
      continue
    }
  }
  return resArr
}

function makeMap (nums: number[]) {
  const map = new Map();
  nums.forEach((num) => {
    const value = map.get(num)
    if (value) {
      map.set(num, value + 1)
    } else {
      map.set(num, 1)
    }
  });
  return map
}

// in-source test suites
if (import.meta.vitest) {
  const { it, expect } = import.meta.vitest
  
  it('test intersection 1', () => {
    debugger
    const nums1 = [1, 2, 2, 1, 3, 9];
    const nums2 = [2, 2];
    // 比较对象还不能用 expect().toBe()，应该使用 toEqual 来比较对象的数据结构
    expect(intersection(nums1, nums2)).toEqual([2, 2])
  })
  it('test 2', () => {
    const nums1 = [3,4,5,6,7]
    const nums2 = [7,7,5,2,3]
    expect(intersection(nums1, nums2)).toEqual([3, 5, 7])
  })
  it('test 3', () => {
    const nums1 = [7, 3,2]
    const nums2 = [7,7,5,2,3]
    expect(intersection(nums1, nums2)).toEqual([7,3,2])
  })
}

LeetCode 链接

https://leetcode.cn/problems/intersection-of-two-arrays-ii/