LeetCode 350. 两个数组的交集 II｜Python 解法详解
CSDN 算法专题 · 数组与哈希表 | 难度：简单
题目信息
- 题号：350
- 难度：简单
- LeetCode：题目链接
题目描述
返回两个数组的交集，每个元素出现次数应等于它在两个数组中出现次数的较小值。
示例
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]约束
数组长度不超过 1000。
解题思路
核心观察
统计较短数组的元素频次，再扫描另一个数组。若当前值剩余次数大于 0，就加入答案并把次数减一，从而严格控制重复数量。
推导与执行步骤
- 统计一个数组的频次
- 扫描另一个数组
- 命中正频次时加入结果
- 对应计数减一
为什么这个方法正确
算法始终围绕上述核心观察维护有效状态，并且每一步只排除已经能够证明不可能产生更优答案的情况。按照执行步骤处理后，所有可能影响答案的元素或节点都会被恰好检查，因此不会遗漏合法答案；状态更新又严格遵守题目约束，所以最终结果有效。
从边界看，空区间、单个元素、全部相同或完全不匹配等情况都会落入初始化条件或循环终止条件，不需要依赖未定义状态。实现时再重点检查下标、空节点和重复元素，即可保证算法在极端输入下仍然成立。
Python 代码
# 解法核心：统计较短数组的元素频次，再扫描另一个数组。若当前值剩余次数大于 0，就加入答案并把次数减一，从而严格控制重复数量。# 实现步骤：# 1. 统计一个数组的频次# 2. 扫描另一个数组# 3. 命中正频次时加入结果# 4. 对应计数减一fromcollectionsimportCounterfromtypingimportListclassSolution:defintersect(self,nums1:List[int],nums2:List[int])->List[int]:iflen(nums1)>len(nums2):nums1,nums2=nums2,nums1 counts=Counter(nums1)# 频次表记录每个元素还可以匹配多少次result=[]# 保存最终答案forvalueinnums2:ifcounts[value]>0:result.append(value)counts[value]-=1returnresult复杂度分析
- 时间复杂度：O(n+m)
- 空间复杂度：O(min(n,m))
易错点
不能直接使用集合，否则会丢失重复次数。
总结
这道题的关键是：统计较短数组的元素频次，再扫描另一个数组。理解这一点后，再结合边界条件检查，代码就能保持清晰且稳定。
