题目描述
给定两个数组，编写一个函数来计算它们的交集。
示例 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，交集为两个相同的元素，不是单个[2]，所以换一种方式，首先对第一个数组建立字典，然后再遍历第二个数组，如果该元素在字典的键中，就把该值加入到结果集中，并在字典中把该键对应的值减1
from collections import Counter
class Solution(object):def intersect(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""if len(nums1) > len(nums2):return self.intersect(nums2, nums1)m = Counter(nums1)intersection = []for i in nums2:if i in m and m[i] > 0:intersection.append(i)m[i] -= 1return intersectionS = Solution()
print(S.intersect([1,2,2,1], [2, 2]))
提升：加入数组是排好序的，怎么优化
很自然的双指针解法，首先两个指针都在数组的起点，如果指针指的两个数相等，则把该数加入结果集。如果其中一个指针所指数小于另一个，就把这个指针向后移
# 扩展，当两个数组排好序后，怎么优化？
from collections import Counter
class Solution(object):def intersect(self, nums1, nums2):intersection = []i = 0; j = 0while i < len(nums1) and j < len(nums2):if nums1[i] == nums2[j]:intersection.append(nums1[i])i += 1j += 1elif nums1[i] < nums2[j]:i += 1elif nums1[i] > nums2[j]:j += 1return intersectionS = Solution()
print(S.intersect([1,1,2,2,3], [2, 2, 3]))