难度: Easy
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]
提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000进阶：
nums1 的大小比 nums2 小，哪种方法更优？nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？运行时间: 19 ms
内存: 16.2 MB
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
ans = []
i = j = 0
n1, n2 = len(nums1), len(nums2)
while i < n1 and j < n2:
if nums1[i] < nums2[j]:
i += 1
elif nums1[i] > nums2[j]:
j += 1
else:
ans.append(nums1[i])
i += 1
j += 1
return ans
该题解的思路是先对两个数组进行排序，然后使用双指针分别指向两个数组的起始位置。然后不断移动指针比较两个指针指向的元素大小，如果相等就把该元素加入答案，并同时移动两个指针；如果不相等，就移动指向较小数字的指针。这样遍历完一遍就能得到两个数组的交集。
时间复杂度: O((n1+n2)log(n1+n2))
空间复杂度: O(log(n1+n2))
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 对两个数组进行排序
nums1.sort()
nums2.sort()
ans = []
i = j = 0
n1, n2 = len(nums1), len(nums2)
# 双指针遍历两个数组
while i < n1 and j < n2:
if nums1[i] < nums2[j]:
# 移动指向较小数字的指针
i += 1
elif nums1[i] > nums2[j]:
# 移动指向较小数字的指针
j += 1
else:
# 如果相等就把该元素加入答案
ans.append(nums1[i])
# 同时移动两个指针
i += 1
j += 1
return ans
选择对数组进行排序而不是使用哈希表的一个原因是排序后使用双指针方法可以在不需要额外空间的情况下找到交集，这对于内存使用较为友好。另外，排序和双指针方法在某些情况下可能比使用哈希表更有效，尤其是当数组已经部分或完全排序时。然而，使用哈希表在时间复杂度上通常更优（O(n)），但在空间复杂度上可能较高，尤其是当元素种类繁多时。
如果两个数组中的元素重复度较高，双指针方法依然有效且效率不会受太大影响。在这种情况下，指针会较频繁地同时向前移动，因此可以快速找到所有的交集元素。排序的时间复杂度是O(n log n)，而遍历和比较的时间复杂度是O(n)，因此整体效率主要取决于排序步骤。
如果`nums1`的大小比`nums2`小，考虑先对`nums1`进行排序然后遍历`nums2`是一个有效的策略。这样做的优势在于减少了排序的时间和空间成本，因为排序较小的数组比较快，且使用较小的数组建立哈希表（如果选择使用哈希表的策略）会占用更少的空间。此外，这种方式可以在遍历较大的数组时直接查找并确定交集元素，减少了不必要的计算和存储操作。
如果`nums2`的元素存储在磁盘上并且内存有限，可以采用外部排序或者分块处理的方法来优化算法。首先，可以对`nums1`进行排序，并将其加载到内存中。然后，将`nums2`分成多个小块，每块单独从磁盘加载并排序，与内存中的`nums1`进行比较和交集查找。这种方法可以有效减少同时加载到内存中的数据量，从而减少内存使用。同时，通过减少对磁盘的全局扫描次数，也能降低IO操作。