349. 两个数组的交集

示例1：

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

示例2：

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

说明：

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

方法一：两个集合

哈希

如果使用哈希集合存储元素，则可以在$O(1)$的时间内判断一个元素是否在集合中，从而降低时间复杂度。

首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合汇总，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到$O(m+n)$。

class Solution:
def intersection(self, nums1, nums2):
	set1 = set(nums1)
	set2 = set(nums2)
	return self.set_intersection(self, set1, set2)
	
def set_intersection(self, set1, set2):
	if len(set1) > len(set2):
		return self.set_intersection(set2, set1)
	return [x for x in set1 if x in set2]

复杂度分析

• 时间复杂度：$O(m+n)$，其中$m$和$n$分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要$O(m+n)$的时间，遍历较小的集合并判断元素是否在另一个集合中需要$O(min(m,n))$的时间，因此总时间复杂度是$O(m+n)$。
• 空间复杂度：$O(m+n)$，其中$m$和$n$分别是两个数组的长度。空间复杂度主要取决于两个集合。

方法二：排序+双指针

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

首先对两个数组进行排序，然后使用两个指针遍历两个数组，可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量$pre$表示上一次加入答案数组的元素。

初始时，两个指针分别指向两个数组的头部，每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于$pre$，将该数字添加到答案并更新$pre$变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

class Solution：
	def intersection(self, nums1, nums2):
		nums1.sort()
		nums2.sort()
		length1, length2 = len(nums1), len(nums2)
		intersection = list()
		index1 = index2 = 0
		while index1 < length1 and index2 < length2:
		num1 = nums1[index1]
		num2 = nums2[index2]
		if not intersection or num1 != intersection[-1]:
			index1 += 1
			index2 += 1
		elif num1 < num2:
			index1 += 1
		else:
			index2 += 1
		return intersection

复杂度分析

• 时间复杂度：$O(mlogn+nlogn)$，其中$m$和$n$分别是两个数组的长度。对两个数组排序的时间复杂度分别是$O(mlogm)$和$O(nlogn)$，双指针寻找