349-两个数组的交集.md

349. 两个数组的交集

leecode原题

题目

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例

示例 1:

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

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

解题思路

如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费

本题虽然还是限制了数组值的范围, 但是我们还是采用其它的思路方法来解决。

思路

我们直接使用golang自带的map，按下述步骤操作:

1. 遍历数组1，将元素作为key值存入map中
2. 遍历数组2，判断元素是否存在map中，存在则是相同元素，并且在map中将该元素对应的key删除(因为最终重复元素只返回一个)

实现

源码

func intersection(nums1 []int, nums2 []int) []int {
	set := make(map[int]struct{})
	arr := make([]int, 0)

	// 数组num1塞入set之中
	for _, v := range nums1 {
		set[v] = struct{}{}
	}
	//遍历数组num2, 找到相同元素
	for _, v := range nums2 {
		if _, ok := set[v]; ok {
			arr = append(arr, v)
			delete(set, v)
		}
	}
	return arr
}