LeetCode 两个数组的交集题解

LeetCode 两个数组的交集题解题目描述给定两个数组编写一个函数来计算它们的交集。示例输入nums1 [1,2,2,1],nums2 [2,2]输出[2]解题思路方法哈希表思路使用哈希表来解决这个问题。首先遍历第一个数组将每个元素存入哈希表中。然后遍历第二个数组对于每个元素如果在哈希表中存在将其加入结果列表并从哈希表中移除该元素。最后返回结果列表。复杂度分析时间复杂度O(m n)其中 m 和 n 分别是两个数组的长度。空间复杂度O(min(m, n))需要额外的空间来存储哈希表。代码实现方法哈希表from collections import defaultdict # 两个数组的交集哈希表 def intersection(nums1, nums2): # 创建哈希表统计 nums1 中每个元素出现的次数 count defaultdict(int) for num in nums1: count[num] 1 # 遍历 nums2找出交集元素 result [] seen set() for num in nums2: if count[num] 0 and num not in seen: result.append(num) seen.add(num) return result # 测试 def test_intersection(): nums1 [1, 2, 2, 1] nums2 [2, 2] print(intersection(nums1, nums2)) # 输出[2] nums1 [4, 9, 5] nums2 [9, 4, 9, 8, 4] print(intersection(nums1, nums2)) # 输出[9, 4] if __name__ __main__: test_intersection()方法集合# 两个数组的交集集合 def intersection_set(nums1, nums2): set1 set(nums1) set2 set(nums2) return list(set1 set2) # 测试 def test_intersection_set(): nums1 [1, 2, 2, 1] nums2 [2, 2] print(intersection_set(nums1, nums2)) # 输出[2] if __name__ __main__: test_intersection_set()测试用例测试用例 1基本情况输入nums1 [1,2,2,1],nums2 [2,2]输出[2]测试用例 2多个交集元素输入nums1 [4,9,5],nums2 [9,4,9,8,4]输出[9,4]总结两个数组的交集是一个经典的哈希表问题它可以通过哈希表或集合来高效地解决。哈希表法的核心思想是使用哈希表统计第一个数组中每个元素出现的次数然后遍历第二个数组找出在哈希表中存在的元素。集合法的核心思想是将两个数组转换为集合然后求交集。掌握哈希表和集合的使用方法对于解决类似的问题非常重要。