哈希算法题目：两个数组的交集 II

字数 2460 2025-10-26 09:00:43

哈希算法题目：两个数组的交集 II

题目描述
给定两个整数数组 nums1 和 nums2，请以数组形式返回它们的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（考虑出现次数）。如果答案不唯一，可以按任意顺序返回。

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

示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
解释：[9,4] 也是可以接受的。

解题过程

这个问题的核心在于，我们需要统计每个元素在两个数组中出现的次数，并取每个元素在两个数组中出现次数的最小值，作为该元素在结果中出现的次数。

步骤 1：理解核心难点
如果只是简单地判断一个元素是否存在于两个数组中（即集合交集），我们可以使用哈希集合。但本题要求考虑元素出现的次数，这意味着我们需要知道每个元素在 nums1 中出现了几次，在 nums2 中出现了几次。因此，我们需要一种能够存储元素及其出现次数的数据结构。

步骤 2：选择合适的数据结构
哈希映射（或称为字典）是解决此类问题的理想工具。它可以将元素（作为键）映射到其出现的次数（作为值）。

思路：我们可以先遍历一个数组，用哈希映射统计其中每个数字出现的频率。然后遍历第二个数组，检查每个数字是否在哈希映射中存在，如果存在，则将该数字添加到结果列表中，并减少哈希映射中该数字的计数。

步骤 3：详细算法步骤
让我们将思路分解为具体步骤：

初始化哈希映射：创建一个空的哈希映射（例如，名为 freqMap），用于记录数字及其出现频率。
统计较小数组的频率（优化步骤）：为了降低空间复杂度，我们通常选择先遍历较小的那个数组来构建哈希映射。这里我们先假设 nums1 是较小的数组（如果不是，我们可以在后续步骤中交换角色）。
- 遍历数组 nums1。
- 对于 nums1 中的每一个数字 num：
  - 如果 num 不在 freqMap 中，我们将其加入映射，并设置其值为 1（freqMap[num] = 1）。
  - 如果 num 已经在 freqMap 中，我们将其对应的值加 1（freqMap[num] += 1）。
遍历第二个数组并构建结果：
- 初始化一个空列表 result 用于存放最终答案。
- 遍历数组 nums2。
- 对于 nums2 中的每一个数字 num：
  - 检查 num 是否存在于 freqMap 中，并且其对应的值（即剩余次数）是否大于 0（freqMap.get(num, 0) > 0）。
  - 如果存在且计数大于 0：
    - 将 num 添加到结果列表 result 中。
    - 将 freqMap 中 num 对应的计数减 1（freqMap[num] -= 1）。这一步非常关键，它确保了我们在结果中添加的 num 的数量不会超过它在 nums1 中出现的次数。例如，如果 nums1 有 2 个 2，nums2 有 3 个 2，我们只应该取 2 个 2 放入结果。
  - 如果不存在或计数已为 0：则忽略这个数字，继续遍历。
返回结果：遍历完成后，返回结果列表 result。

步骤 4：通过示例验证算法
让我们用示例 1 来走一遍流程：
nums1 = [1,2,2,1]
nums2 = [2,2]

构建 freqMap（基于 nums1）:
- 遇到 1: freqMap{1: 1}
- 遇到 2: freqMap{1: 1, 2: 1}
- 遇到 2: freqMap{1: 1, 2: 2}
- 遇到 1: freqMap{1: 2, 2: 2}
遍历 nums2 并构建结果:
- 遇到第一个 2: 存在于 freqMap 且计数为 2 > 0。将 2 加入 result，freqMap[2] 减为 1。result = [2]
- 遇到第二个 2: 存在于 freqMap 且计数为 1 > 0。将 2 加入 result，freqMap[2] 减为 0。result = [2, 2]
返回结果 [2, 2]。

步骤 5：复杂度分析

时间复杂度：O(m + n)。其中 m 和 n 分别是数组 nums1 和 nums2 的长度。我们分别遍历了两个数组各一次。哈希映射的插入和查找操作平均时间复杂度为 O(1)。
空间复杂度：O(min(m, n))。我们使用哈希映射来存储较小数组的元素及其出现频率。

步骤 6：进阶思考（如果数组已排序）
题目有时会提出一个进阶问题：如果给定的数组已经是有序的，你将如何优化你的算法？

优化算法：如果两个数组都是有序的，我们可以使用双指针法，从而避免使用额外的哈希映射空间。
- 初始化两个指针 i 和 j，分别指向 nums1 和 nums2 的起始位置。
- 当 i < len(nums1) 且 j < len(nums2) 时：
  - 如果 nums1[i] == nums2[j]，说明找到了一个交集元素，将其加入结果，然后 i 和 j 同时后移（i++, j++）。
  - 如果 nums1[i] < nums2[j]，说明 nums1[i] 太小了，需要增大它，所以 i 后移（i++）。
  - 如果 nums1[i] > nums2[j]，说明 nums2[j] 太小了，需要增大它，所以 j 后移（j++）。
复杂度分析：
- 时间复杂度：O(m + n)。最坏情况下，我们需要遍历两个数组的所有元素。
- 空间复杂度：O(1)。除了存储结果的列表外，我们只使用了常数级别的额外空间。这是一种空间上的优化。

哈希算法题目：两个数组的交集 II 题目描述给定两个整数数组 nums1 和 nums2，请以数组形式返回它们的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（考虑出现次数）。如果答案不唯一，可以按任意顺序返回。示例 1: 输入：nums1 = [ 1,2,2,1], nums2 = [ 2,2 ] 输出：[ 2,2 ] 示例 2: 输入：nums1 = [ 4,9,5], nums2 = [ 9,4,9,8,4 ] 输出：[ 4,9 ] 解释：[ 9,4 ] 也是可以接受的。解题过程这个问题的核心在于，我们需要统计每个元素在两个数组中出现的次数，并取每个元素在两个数组中出现次数的最小值，作为该元素在结果中出现的次数。步骤 1：理解核心难点如果只是简单地判断一个元素是否存在于两个数组中（即集合交集），我们可以使用哈希集合。但本题要求考虑元素出现的次数，这意味着我们需要知道每个元素在 nums1 中出现了几次，在 nums2 中出现了几次。因此，我们需要一种能够存储元素及其出现次数的数据结构。步骤 2：选择合适的数据结构哈希映射（或称为字典）是解决此类问题的理想工具。它可以将元素（作为键）映射到其出现的次数（作为值）。思路：我们可以先遍历一个数组，用哈希映射统计其中每个数字出现的频率。然后遍历第二个数组，检查每个数字是否在哈希映射中存在，如果存在，则将该数字添加到结果列表中，并减少哈希映射中该数字的计数。步骤 3：详细算法步骤让我们将思路分解为具体步骤：初始化哈希映射：创建一个空的哈希映射（例如，名为 freqMap ），用于记录数字及其出现频率。统计较小数组的频率（优化步骤）：为了降低空间复杂度，我们通常选择先遍历较小的那个数组来构建哈希映射。这里我们先假设 nums1 是较小的数组（如果不是，我们可以在后续步骤中交换角色）。遍历数组 nums1 。对于 nums1 中的每一个数字 num ：如果 num 不在 freqMap 中，我们将其加入映射，并设置其值为 1（ freqMap[num] = 1 ）。如果 num 已经在 freqMap 中，我们将其对应的值加 1（ freqMap[num] += 1 ）。遍历第二个数组并构建结果：初始化一个空列表 result 用于存放最终答案。遍历数组 nums2 。对于 nums2 中的每一个数字 num ：检查 num 是否存在于 freqMap 中，并且其对应的值（即剩余次数）是否大于 0（ freqMap.get(num, 0) > 0 ）。如果存在且计数大于 0 ：将 num 添加到结果列表 result 中。将 freqMap 中 num 对应的计数减 1（ freqMap[num] -= 1 ）。这一步非常关键，它确保了我们在结果中添加的 num 的数量不会超过它在 nums1 中出现的次数。例如，如果 nums1 有 2 个 2 ， nums2 有 3 个 2 ，我们只应该取 2 个 2 放入结果。如果不存在或计数已为 0 ：则忽略这个数字，继续遍历。返回结果：遍历完成后，返回结果列表 result 。步骤 4：通过示例验证算法让我们用示例 1 来走一遍流程： nums1 = [ 1,2,2,1 ] nums2 = [ 2,2 ] 构建 freqMap （基于 nums1 ）: 遇到 1: freqMap{1: 1} 遇到 2: freqMap{1: 1, 2: 1} 遇到 2: freqMap{1: 1, 2: 2} 遇到 1: freqMap{1: 2, 2: 2} 遍历 nums2 并构建结果: 遇到第一个 2: 存在于 freqMap 且计数为 2 > 0。将 2 加入 result ， freqMap[2] 减为 1。 result = [2] 遇到第二个 2: 存在于 freqMap 且计数为 1 > 0。将 2 加入 result ， freqMap[2] 减为 0。 result = [2, 2] 返回结果 [2, 2] 。步骤 5：复杂度分析时间复杂度：O(m + n) 。其中 m 和 n 分别是数组 nums1 和 nums2 的长度。我们分别遍历了两个数组各一次。哈希映射的插入和查找操作平均时间复杂度为 O(1)。空间复杂度：O(min(m, n)) 。我们使用哈希映射来存储较小数组的元素及其出现频率。步骤 6：进阶思考（如果数组已排序）题目有时会提出一个进阶问题：如果给定的数组已经是有序的，你将如何优化你的算法？优化算法：如果两个数组都是有序的，我们可以使用双指针法，从而避免使用额外的哈希映射空间。初始化两个指针 i 和 j ，分别指向 nums1 和 nums2 的起始位置。当 i < len(nums1) 且 j < len(nums2) 时：如果 nums1[i] == nums2[j] ，说明找到了一个交集元素，将其加入结果，然后 i 和 j 同时后移（ i++, j++ ）。如果 nums1[i] < nums2[j] ，说明 nums1[i] 太小了，需要增大它，所以 i 后移（ i++ ）。如果 nums1[i] > nums2[j] ，说明 nums2[j] 太小了，需要增大它，所以 j 后移（ j++ ）。复杂度分析：时间复杂度：O(m + n) 。最坏情况下，我们需要遍历两个数组的所有元素。空间复杂度：O(1) 。除了存储结果的列表外，我们只使用了常数级别的额外空间。这是一种空间上的优化。