LeetCode 350、两个数组的交集II

LeetCode 350、两个数组的交集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]

提示： 1 <= nums1.length, nums2.length <= 1000 0 <= nums1[i], nums2[i] <= 1000

题目解析

解题思路

题目要求返回两个数组的交集，且每个元素出现的次数取两数组中该元素出现次数的较小值。参考代码采用哈希表（Counter）统计频率的方法：先用两个 Counter 分别统计 nums1 和 nums2 中每个元素的出现次数，然后遍历其中一个 Counter 的键，对于每个键 k，取 min(cnt1[k], cnt2[k]) 作为该元素在交集中应出现的次数，最后用列表乘法生成对应数量的 k 并拼接到结果列表中。

关键步骤

1. 频率统计：使用 Counter(nums1) 和 Counter(nums2) 得到两个哈希表，键为元素值，值为出现次数。 2. 遍历与取较小值：遍历 cnt1 的键（也可遍历 cnt2，效果相同），对每个键 k 计算 min(cnt1[k], cnt2[k])。若 k 不在 cnt2 中，cnt2[k] 返回 0，取 min 后为 0，不会加入结果。 3. 构造结果列表：[k] * min(cnt1[k], cnt2[k]) 生成包含 min 个 k 的列表，通过 ans += ... 将其追加到 ans 中。

例如，nums1 = [1,2,2,1]，nums2 = [2,2]：

cnt1 = {1:2, 2:2}
cnt2 = {2:2}
遍历 cnt1 的键：
  k=1: min(2,0)=0 → 不添加
  k=2: min(2,2)=2 → [2]*2 = [2,2] → ans=[2,2]

复杂度分析

• 时间复杂度：O(n + m)，其中 n、m 分别为两数组长度。统计频率需 O(n+m)，遍历键的个数不超过 n 或 m，总体线性。
• 空间复杂度：O(n + m)，两个哈希表分别存储两数组中不重复的元素及其频率，最坏情况下每个元素都不同，空间与数组长度成正比。结果列表不计入额外空间（题目要求返回）。