LeetCode 349：两个数组的交集
题意
给定两个数组，计算它们的交集。
示例
输入：nums1 = [4, 9, 5]，nums2 = [9, 4, 9, 8, 4]
输出：[９, 4]
提示
输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
题目解析
求两个数组的交集，直白点儿就是【nums2 的元素是否在 nums1 中】。
第一种解法
这道题字符串 num1 和 num2 仅包含1000以内，数字就固定的 1000个。
（不要我问我为什么1000以内，因为你has设到100以内报错~）
这种定长的范围且和字符次数相关，用哈希妥妥的没问题。
第一种解法 使用的哈希函数 f(key) = key - 0 。 （这道题思路沿用了242有效字母的异位词~） 哈希函数找好，下面的就很简单：
- 遍历字符串 num1，哈希表hash1对应的字符值加。
- 遍历字符串 num2，哈希表hash2对应的字符值加。
- 判断哈希表hash1不为0，并且hash2也不为0，则把重复的数字输送到result序列
代码实现
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: hash1=[0]*1000 for i in range(len(nums1)): hash1[nums1[i]-0] +=1 hash2=[0]*1000 for i in range(len(nums2)): hash2[nums2[i]-0] +=1 result=[] for i in range(1000): if hash1[i] != 0: if hash2[i] != 0: result.append(i) return result 复制代码
网络异常，图片无法展示
|
第二种解法
这道题同样也没限制数值的大小，所以就不能用数组来做哈希表。
碰到这种对目前来说是未知数值大小的情况，我们可以使用集合 set 来解决。
代码实现
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: # 有一个数组为空，则交集为空 if not nums1 or not nums2: return [] # 初始化哈希表 hash = {} # 初始化结果列表，存放最后结果 res = [] # 哈希表 key 为 nums1 数组中的数，value 为值 for i in nums1: if not hash.get(i): hash[i] = 1 # 遍历 nums，如果 nums2 数组中的数出现在哈希表中，对应数放入结果列表，对应 value 值置-为0 for j in nums2: if hash.get(j): res.append(j) hash[j] = 0 return res
