两个数组的交集（350）

题目

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

举例

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

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

算法

Map

使用Map存储第一个数组中数字出现的次数，然后在第二个数组中匹配Map中对应的key，一旦匹配成功，将对应的value--，并将key推入结果数组

function intersect(nums1, nums2) {
  let map = {}
  let res = []
  for(let i = 0; i < nums1.length; i++) {
    if(!map[nums1[i]]) {
      map[nums1[i]] = 1
    } else {
      map[nums1[i]]++
    }
  }
  for(let i = 0; i < nums2.length; i++) {
    if(map[nums2[i]]) {
      res.push(nums2[i])
      map[nums2[i]]--
    }
  }
  return res
}

双指针

两个数组都是由小至大递增，使用指针滑动判断当前两数组元素大小，如不同，则指向小值的指针滑动；若相同，则同时滑动并将值推入结果数组

function intersect(nums1, nums2) {
  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)
  let res = []
  let i = 0, j = 0
  while(i < nums1.length && j < nums2.length) {
    if(nums1[i] < nums2[j]) {
      i++
    } else if (nums1[i] > nums2[j]) {
      j++
    } else {
      res.push(nums1[i])
      i++
      j++
    }
  }
  return res
}