题目描述
思路解析动画文字版
记住口诀：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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题