力扣-第349题--两个数组的交集（python）--逐步解析

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

网址：
https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/acm-xuan-shou-tu-jie-leetcode-liang-ge-s-qzbi/

就一句话：求两个数组的交集，直白点儿就是【nums2 的元素是否在 nums1 中】。
需要注意一下“提示”里讲的：输出结果中的每个元素一定是唯一的，翻译一下就是去重输出。

代码逐步解析：

class Solution:
    def intersection(self, nums1, nums2):

        # 有一个数组为空，则交集为空
        if not nums1 or not nums2:
            return []

        # 初始化哈希表
        hash = {}
        # 初始化结果列表，存放最后结果
        res = []

        # 哈希表 key 为 nums1 数组中的数，value 为值
        for i in nums1:
            print('i',i)

            print('hash.get(i):',hash.get(i))
            if not hash.get(i):
                hash[i] = 1
                print('hash-i:', hash)

        # 遍历 nums，如果 nums2 数组中的数出现在哈希表中，对应数放入结果列表，对应 value 值置-为0
        for j in nums2:
            print('j',j)

            print('hash.get(j):',hash.get(j))
            if hash.get(j):
                res.append(j)
                hash[j] = 0
                print('hash-j:', hash)

        print('hash:', hash)

        return res


if __name__ == '__main__':
    s = Solution()
    nums1 = [1, 2, 2, 1]
    nums2 = [2, 5]

    result_list = s.intersection(nums1, nums2)
    print('result_list:', result_list)

输出为：

i 1
hash.get(i): None
hash-i: {1: 1}

i 2
hash.get(i): None
hash-i: {1: 1, 2: 1}

i 2
hash.get(i): 1

i 1
hash.get(i): 1

j 2
hash.get(j): 1
hash-j: {1: 1, 2: 0}

j 5
hash.get(j): None
hash: {1: 1, 2: 0}

result_list: [2]

• 图解：
  以 nums1 = [4, 9, 5]，nums2 = [9, 4, 9, 8, 4] 为例。
  首先初始化一个哈希表和一个结果列表。

# 初始化哈希表
hash = {}
# 初始化结果列表，存放最后结果
res = []

第一步，遍历数组 nums1，将出现的数存进哈希表中。
nums1 数组中，第 1 个元素为 4，将其加入哈希表，对应数值置为 1。

# 哈希表 key 为 nums1 数组中的数，value 为值
for i in nums1:
    if not hash.get(i):
        hash[i] = 1

因为【输出结果中的每个元素一定是唯一的】，所以对于 key 所对应的 value 来说“数值是多少”就无所谓了，所以在本题中，不管某个元素在数组中出现多少次，我把 value 都置为 1。
遍历完数组 nums1，哈希表如下图所示：

第二步，遍历 nums2 数组，nums2 数组中的元素如果出现在哈希表中，则证明是和 nums1 数组相交的元素，则加入结果列表中。
nums2 数组中，第 1 个元素为 9，9 在哈希表中，则元素 9 加入结果列表，哈希表中该元素置为 0。

# 遍历 nums，如果 nums2 数组中的数出现在哈希表中，对应数放入结果列表，对应 value 值置-为0
for j in nums2:
    if hash.get(j):
        res.append(j)
        hash[j] = 0

同样遍历完 nums2，最后的结果变为下图所示：

res 就是最终的结果。

本题解遍历了 nums1 和 nums2 数组，所以时间复杂度为 O(n + m)，n 和 m 分别为两个数组的长度。
额外建了一个哈希表，所以空间复杂度为 O(max(n, m))。