89 - 两个数组的交集

题目

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

示例 1:

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

示例 2:

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

说明:

输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

解答

可以写个双循环，不过这成本有些太高了；也可以存一个哈希表，空间换时间

set

官网提出了set的做法，可以先排除不一样的数

const findAll = function (set1, set2) {
  const result = []
  for (const item of set1) {
    for (const inner_item of set2) {
      if (item === inner_item) {
        result.push(item)
      }
    }
  }
  return result
}

var intersection = function (nums1, nums2) {
  const set1 = new Set(nums1)
  const set2 = new Set(nums2)
  if (set1.size < set2.size) {
    return findAll(set1, set2)
  } else {
    return findAll(set2, set1)
  }
};

Runtime: 68 ms, faster than 22.11% of JavaScript online submissions for Intersection of Two Arrays.

Memory Usage: 36.4 MB, less than 7.69% of JavaScript online submissions for Intersection of Two Arrays.

出奇的慢。。

作者：zhl1232

链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/js-xie-leetcode-by-zhl1232-9/

这位大佬同样用set写出了不一样的解法

var intersection = function (nums1, nums2) {
  let hash1 = new Set(nums1)
  let hash2 = new Set()

  for (let i = 0; i < nums2.length; i++) {
    if (hash1.has(nums2[i])) {
      hash2.add(nums2[i])
    }
  }
  return [...hash2]
};

Runtime: 56 ms, faster than 77.57% of JavaScript online submissions for Intersection of Two Arrays.

Memory Usage: 34.3 MB, less than 53.85% of JavaScript online submissions for Intersection of Two Arrays.

很酷吼

感觉我绕远路了

func intersection(nums1 []int, nums2 []int) []int {
    data := make(map[int]bool)
    reMap := make(map[int]bool)
    for _, elem := range nums1 {
        data[elem] = true
    }
    for _, elem := range nums2 {
        if _, ok := data[elem]; ok {
            reMap[elem] = true
        }
    }
    result := make([]int, 0, len(reMap))
    for i := range reMap {
        result = append(result, i)
    }
    return result
}

Runtime: 4 ms, faster than 86.09% of Go online submissions for Intersection of Two Arrays.

Memory Usage: 4.5 MB, less than 100.00% of Go online submissions for Intersection of Two Arrays.