题目描述
思路解析
一句话答案：LeetCode 350 两个数组的交集 II 用哈希计数：先把 nums1 的每个数记进计数表，再扫 nums2 命中就取一个、计数减 1，重复次数天然带上，时间 O(n+m)、空间 O(n)。
结果该留几个 9，带重复的交集
给两个数组 nums1、nums2，返回交集，但和普通求交不一样：一个数在两边都出现，结果要保留它在两数组中出现次数的较小值。题面 nums1=[4,9,5,9]、nums2=[9,4,9,8,4,5]，9 在两边各出现 2 次，结果就带 2 个 9；4 和 5 各 1 次，各留 1 个，输出 [9,4,9,5]。
回 nums1 线扫配对，为什么撑不住
拿 nums2 里每个数，回 nums1 从头找一个还没被认领的相同值，配上就把那个位置划掉。nums1 有 n 个数、nums2 有 m 个，每次配对都可能扫遍 nums1，最坏 O(n·m)（大 O 记号，记操作量随规模的放大），两数组一大就吃力。有人想转成集合求交、一行搞定，可去重后 9 只剩一个，丢掉「9 出现两次」这层重复，本题偏要带重复，也不对。
只要知道每个数还剩几个能配
慢就慢在每次都回 nums1 线扫，其实只要知道 nums1 里每个数还剩几个能配就够了。把 nums1 过一遍，用一张计数表（哈希表，键是数值、值是它在 nums1 出现的次数）记下每个数出现几次。为什么记次数、不只记「出现过」——交集要保留较小的出现次数，9 在 nums1 有 2 个，最多配出 2 个 9；只记「出现过」等于把次数拍成 1，多出来那个 9 就配不上。
扫 nums2 配一个、扣一个名额
接着扫 nums2，每个数 x 查 cnt[x]：大于 0 说明 nums1 还留着一个没配的 x，收进答案，再把 cnt[x] 减 1，用掉一个名额；等于 0 说明没有或已配完，跳过不收。减 1 是重复次数不出错的关键——收一个扣一个，同一个 x 在 nums2 出现多次时，只能配到 nums1 里剩的那几个，扣光就再也配不上。扫完 nums2 就得到答案。
nums1=[4,9,5,9] 配 nums2，逐个查表
拿 nums1=[4,9,5,9]、nums2=[9,4,9,8,4,5] 走一遍。先建表：扫 nums1 得 cnt={4:1, 9:2, 5:1}。再扫 nums2。第一个 9，cnt[9]=2>0，收下、cnt[9] 减成 1。第二个 4，cnt[4]=1>0，收下、cnt[4] 减成 0。第三个 9，cnt[9]=1>0，收下、cnt[9] 减成 0。第四个 8，cnt[8]=0，跳过；第五个 4，cnt[4] 已是 0，跳过。第六个 5，cnt[5]=1>0，收下、cnt[5] 减成 0。答案 [9,4,9,5]：9 配 2 个、4 和 5 各 1 个，正是两边较小的出现次数。
减 1 那步漏掉，重复的数被反复领走
建表扫 nums1、配对扫 nums2，两趟都是线性，时间 O(n+m)；计数表只装 nums1 出现过的数，空间 O(n)。配对后漏了 cnt[x] 减 1，同一个名额会被 nums2 里重复的数反复领走，答案多出一堆重复。用集合去重再求交能糊弄过「交集 I」，这题会把重复全抹平、9 只剩一个。边界先想清：两数组毫无公共值时答案为空；有一个数组为空时交集必空；两数组相同时结果就是整份数组。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住口诀：nums1 建计数表，nums2 来配对，配一个扣一个。下面每帧都在套它。
先把 nums1 做成计数表。现在读到 nums1[0] = 4，下一帧把它的计数加 1。
4 的计数更新成 1。计数表记的是「这个数在 nums1 里还剩几次能配」。
先把 nums1 做成计数表。现在读到 nums1[1] = 9，下一帧把它的计数加 1。
9 的计数更新成 1。计数表记的是「这个数在 nums1 里还剩几次能配」。
先把 nums1 做成计数表。现在读到 nums1[2] = 5，下一帧把它的计数加 1。
5 的计数更新成 1。计数表记的是「这个数在 nums1 里还剩几次能配」。
先把 nums1 做成计数表。现在读到 nums1[3] = 9，下一帧把它的计数加 1。
9 的计数更新成 2。计数表记的是「这个数在 nums1 里还剩几次能配」。
nums1 的计数表全部建好了。接下来扫 nums2，每个数来表里「认领」名额。
扫到 nums2[0] = 9，去计数表里查它还剩几个名额：cnt[9] = 2。
cnt[9] 原来大于 0，说明 nums1 那边还留着一个 9，配上！收进答案，并把 cnt[9] 扣成 1。
扫到 nums2[1] = 4，去计数表里查它还剩几个名额：cnt[4] = 1。
cnt[4] 原来大于 0，说明 nums1 那边还留着一个 4，配上！收进答案，并把 cnt[4] 扣成 0。
扫到 nums2[2] = 9，去计数表里查它还剩几个名额：cnt[9] = 1。
cnt[9] 原来大于 0，说明 nums1 那边还留着一个 9，配上！收进答案，并把 cnt[9] 扣成 0。
扫到 nums2[3] = 8，去计数表里查它还剩几个名额：cnt[8] = 0。
cnt[8] 已经是 0，nums1 那边没有多余的 8 了，跳过这个，不进答案。
扫到 nums2[4] = 4，去计数表里查它还剩几个名额：cnt[4] = 0。
cnt[4] 已经是 0，nums1 那边没有多余的 4 了，跳过这个，不进答案。
扫到 nums2[5] = 5，去计数表里查它还剩几个名额：cnt[5] = 1。
cnt[5] 原来大于 0，说明 nums1 那边还留着一个 5，配上！收进答案，并把 cnt[5] 扣成 0。
nums2 全部扫完，答案是 [9,4,9,5]。9 配到 2 个、4 和 5 各 1 个，正好是两边出现次数的较小值。
边界先想清：无交集、空数组、两数组完全相同。
面试重点：带重复用计数表，大文件用流式扫描。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: cnt = Counter(nums1) ans = [] for x in nums2: if cnt[x]: ans.append(x) cnt[x] -= 1 return ans复杂度
- 时间：O(n + m)，建表扫 nums1，配对扫 nums2，各一遍
- 空间：O(n)，计数表存 nums1 里出现的数
易错点
面试追问把动画讲成自己的话
追问如果 nums1 很小、nums2 是磁盘上的超大文件读不进内存怎么办？
追问这题和「交集 I」有什么区别？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
有效的完全平方数
LeetCode 367 · 简单 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题