350。IntersectionofTwoArraysII题目来源：LeetCodehttps://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和第一条语句【输出结果中每个元素出现的次数要和两个中元素出现的次数一致arrays]，因此我们知道同一个数字可能在两个数组中出现多次。哈希表这里先说一下哈希表的思想。我们可以使用哈希表来存储每个数字出现的次数。这里，我们要求两个数组的交集，那么这里的数字出现的次数取决于两个数组中出现次数较少的部分。这里，我们可以考虑遍历一个更短的数组，在哈希表中记录数字和对应的出现次数。然后再遍历另一个数组，如果哈希表中存在该数，则将该数添加到结果列表中，然后将哈希表中该数对应的次数减1。（这里我们选择遍历较短的数组来保存哈希表，考虑降低空间复杂度。）哈希表的思想示意图如下（例2）：具体实现代码见【代码实现#哈希表】双指针的题目后进阶部分的第一个问题，如果数组已经排序，如何优化算法？这里，我们可以考虑使用双指针的方法。双指针思想的算法大致如下：首先定义双指针，分别指向两个数组的首元素。开始比较双指针指向的元素，处理如下情况：如果两个元素不相等，则指针指向较小的元素，向后移动；如果两个元素相等，则将该元素添加到结果列表中，然后两只手同时向后移动。当任何一个指针到达终点时，遍历结束。关于双指针思想的图解如下（例2）：具体实现代码见【代码实现#双指针】这里对第三个进阶题做了大致的解释。如果将nums2的元素存放在磁盘上，磁盘内存是有限的，不可能一次性把所有元素加载到内存中。那么这时候就无法快速排序了，所以推荐使用哈希表的思想。哈希表的思路，数组涉及到查询操作，可以考虑读取部分信息进行处理。代码实现#哈希表类解决方案：defintersect(self,nums1:List[int],nums2:List[int])->List[int]:#遍历较短的数组并将元素存储在哈希表中#确保如果len(nums1)>len(nums2):self.intersect(nums2,nums1)hash_map={}fornuminnums1:ifnumnotinhash_map:hash_map[num]=0hash_map[num]+=1ans=[]fornuminnums2:#检查哈希表中是否存在count=hash_map.get(num,0)#如果元素存在于哈希表中，则将其添加到结果列表中#然后将数字放入如果count>0，对应于哈希表的元素的出现次数减一：ans.append(num)hash_map[num]-=1returnans#doublepointerclass解决方案：defintersect(self,nums1:List[int],nums2:List[int])->List[int]:nums1.sort()nums2.sort()p=q=0ans=[]#任意指针到达数组末尾，结束遍历whilep
