349 求两个数组的交集

题意：给定两个数组，编写一个函数来计算它们的交集。注意：输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
使用数组做哈希题目（或者说这种索引对应元素的），是因为题目都限制了数值的大小。刚好这道题目的提示部分限制了数组长度以及数组中元素的大小，所以可以用数组。思路同上一题。
时间复杂度 O(n) 空间复杂度O(1)

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""# 数组解法# 为什么可以用数组？因为题目当中限制是数组长度以及数组中元素取值范围# 1 <= nums1.length, nums2.length <= 1000# 0 <= nums1[i], nums2[i] <= 1000temp1_list = [0]*1001temp2_list = [0]*1001for i in range(len(nums1)):temp1_list[nums1[i]] += 1for i in range(len(nums2)):temp2_list[nums2[i]] += 1result = []for i in range(1001):if temp1_list[i]*temp2_list[i] != 0:result.append(i)return result

如果没有限制数组大小及数组元素大小呢？——>使用字典和集合结合的方法。

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""# 如果没有限制呢? ——> 使用字典和集合# 定义一个字段 键为数组元素的值 值为元素出现次数tabel = {}for i in nums1:tabel[i] = tabel.get(i, 0) + 1result = set() # 定义一个集合来存储结果for i in nums2:if i in tabel:result.add(i) # 将该元素添加到集合中del tabel[i] # 删除该键return list(result) # 注意最终返回的是列表

时间复杂度：O(n)、空间复杂度：O(1)
一种更简单的方法——>直接使用集合，取交集

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""return list(set(nums1)&set(nums2))