350. 两个数组的交集 II
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
题目
给定两个数组，编写一个函数来计算它们的交集。
示例 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 和第一条说明【输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致】，由此我们知道，同一个数字在两个数组中，都有可能出现多次。
哈希表
在这里，我们先说哈希表的思路。我们可以使用哈希表来存储每个数字出现的次数。在这里，我们要求两个数组的交集，那么这里数字出现的次数取决于两个数组中出现次数较小的部分。
在这里，我们可以考虑对较短的数组进行遍历，在哈希表中记录数字以及对应出现的次数。然后再遍历另外一个数组，如果数字存在于哈希表中，那么将数字添加到结果列表中，然后将哈希表对应数字的次数减 1。（这里选择对较短数组进行遍历存哈希表，考虑的是降低空间复杂度。）
关于哈希表思路的图解如下（示例 2）：
[图片上传失败...(image-1dc7d7-1594637184563)]
具体实现代码见【代码实现 # 哈希表】
双指针
在题目后面的进阶当中第一个问题，提到如果数组都是已经排好序的，该如何优化算法？
在这里，我们可以考虑使用双指针的方法。双指针思路的算法大致如下：
- 首先定义双指针，分别指向两个数组的首元素。
- 开始比较双指针指向的元素，对以下的情况进行处理：
- 如果两个元素不相等，指针指向元素较小的向后移动；
- 如果两个元素相等，则将元素添加到结果列表中，然后两个指针同时向后移动。
- 当任意指针到达末尾时，结束遍历。
关于双指针思路的图解如下（示例 2）：
[图片上传失败...(image-11dd6a-1594637184563)]
具体实现代码见【代码实现 # 双指针】
在这里，针对进阶的第三个问题大致的说明下。如果出现 nums2 的元素存储在磁盘上，磁盘内存有限，无法一次加载所有的元素到内存中。那么此时想要快速进行排序，则不太可能，所以建议使用哈希表的思路。针对哈希表的思路，数组涉及的是查询操作，可以考虑读取部分信息进行处理。
代码实现
# 哈希表
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
# 针对较短数组进行遍历将元素存于哈希表中
# 保证前面的数组较短
if len(nums1) > len(nums2):
self.intersect(nums2, nums1)
hash_map = {}
for num in nums1:
if num not in hash_map:
hash_map[num] = 0
hash_map[num] += 1
ans = []
for num in nums2:
# 查看是否存在于哈希表中
count = hash_map.get(num, 0)
# 元素存在于哈希表中，则添加入结果列表中
# 然后将哈希表对应的元素出现次数减一
if count > 0:
ans.append(num)
hash_map[num]-=1
return ans
# 双指针
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
p = q = 0
ans = []
# 任意指针到达数组末尾，结束遍历
while p < len(nums1) and q < len(nums2):
# 在这里，先判断指针对应元素的大小
# 当不相等时，指针对应元素小的移动
# 相等时，将元素放入结果列表中，同时移动指针
if nums1[p] > nums2[q]:
q+=1
elif nums1[p] < nums2[q]:
p += 1
else:
ans.append(nums1[p])
p += 1
q += 1
return ans
实现结果
哈希表|实现结果
双指针|实现结果
欢迎关注
公众号 【书所集录】
