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