349.两个数组的交集

一、问题描述

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

示例 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 的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，该怎么办？

二、方案一：哈希表

1、思路

最直接的方法是使用两个循环遍历两个数组，找出共同的元素。为了确保结果中每个元素出现的次数与在两个数组中出现次数的最小值一致，我们需要记录每个元素在两个数组中出现的次数。

2、代码实现

func intersection(nums1 []int, nums2 []int) []int {
	set := make(map[int]struct{})
	res := make([]int, 0)
	for _, v := range nums1 {
		set[v] = struct{}{}
	}
	for _, v := range nums2 {
		if _, ok := set[v]; ok {
			res = append(res, v)
			// 去重
			delete(set, v)
		}
	}

	return res
}

3、复杂度分析

• 时间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度。我们需要遍历两个数组来构建哈希表，然后再次遍历哈希表来构建结果数组。
• 空间复杂度：O(m+n)，用于存储两个哈希表。

三、方案二：排序和双指针

1、思路

如果两个数组已经排好序，我们可以使用双指针方法来找到交集。首先对两个数组进行排序，然后使用两个指针分别遍历两个数组。在每一步中，我们将两个指针指向的元素进行比较，根据比较结果移动指针。

2、代码实现

func intersection(nums1 []int, nums2 []int) (result []int) {
	sort.Ints(nums1)
	sort.Ints(nums2)
	i, j := 0, 0
	for i < len(nums1) && j < len(nums2) {
		if nums1[i] < nums2[j] {
			i++
		} else if nums1[i] > nums2[j] {
			j++
		} else {
			// 去重
			if len(result) == 0 || nums1[i] > result[len(result)-1] {
				result = append(result, nums1[i])
			}
			i++
			j++
		}
	}
	return result
}

3、复杂度分析

• 时间复杂度：O(mlog(m) + nlog(n))，其中 m 和 n 分别是两个数组的长度。我们需要对两个数组进行排序，然后使用双指针遍历。
• 空间复杂度：O(m+n)，用于存储结果数组。

四、总结

方案	时间复杂度	空间复杂度
哈希表法	O(m+n)	O(m+n)
排序和双指针	O(mlog(m) + nlog(n))	O(m+n)

当两个数组已经排好序时，排序和双指针方法更优。如果两个数组的大小差异很大，那么暴力法可能更合适，因为它不需要对较大的数组进行排序。如果数组存储在磁盘上，且内存有限，我们可能需要使用外部排序算法来处理这个问题。