349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

1. 明知道不科学，但是还是忍不住试一试的暴力搜索

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = []
        for i in nums1:
            if i in nums2:
                res.append(i)
        return list(set(res))

改成一行的

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:        
        return list(set([i for i in nums1 if i in nums2]))

使用set，并且保证遍历的是较短数组

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: 
        if len(nums1) > len(nums2):
            nums1, nums2 = set(nums2), set(nums1)
        else:
            nums1, nums2 = set(nums1), set(nums2)
        return list(set([i for i in nums1 if i in nums2]))

2. 官方题解就是厉害，暴力搜索也是可以再优化的链接

如果使用哈希集合存储元素，则可以在 O(1)O(1) 的时间内判断一个元素是否在集合中，从而降低时间复杂度。

首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到 O(m+n)。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        return self.set_intersection(set1, set2)

    def set_intersection(self, set1, set2):
        if len(set1) > len(set2):
            return self.set_intersection(set2, set1)
        return [x for x in set1 if x in set2]

官方题解之 —— 排序 + 双指针（是我不会的方法）

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 表示上一次加入答案数组的元素。

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 ，将该数字添加到答案并更新 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

看了题解思路后的编码

    nums1, nums2 = sorted(nums1), sorted(nums2)
    res = set()
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            res.add(nums2[j])
            i, j = i + 1, j + 1
        elif nums1[i] < nums2[j]:
            i = i + 1
        elif nums1[i] > nums2[j]:
            j = j + 1
    return list(res)

官方题解

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        length1, length2 = len(nums1), len(nums2)
        intersection = list()
        index1 = index2 = 0
        while index1 < length1 and index2 < length2:
            num1 = nums1[index1]
            num2 = nums2[index2]
            if num1 == num2:
                # 保证加入元素的唯一性
                if not intersection or num1 != intersection[-1]:
                    intersection.append(num1)
                index1 += 1
                index2 += 1
            elif num1 < num2:
                index1 += 1
            else:
                index2 += 1
        return intersection

哈希方法

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: 
        res = dict()
        for k in set(nums1):
                res[k] = 1
        for k in set(nums2):
            if k in res:
                res[k] = res[k] + 1
            else:
                res[k] = 1         
        return [k for k in res.keys() if res[k] > 1]

题解区的奇技淫巧

class Solution:
   def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
       return list(set(nums1)&set(nums2))