题目描述
思路解析动画文字版
记牢这一句:一边扫一边往两个已见集合里登记,谁两边都露过面,谁就是公共数,当前公共数的个数就是 C[i]。因为是排列,每个数最多出现一次,判断非常干净。下面从下标 0 开始扫。
开局 · 两个已见集合都为空：这是数组 A,紫色指针待会儿会从最左边一格一格往右挪。右边这张登记表现在是空的,它记录每个数字目前落在哪一侧:只在 A 出现记 A 侧,只在 B 出现记 B 侧,两边都出现就升级成 A·B 公共。C[i] 就是表里公共那类有几个。开局两个集合都空,公共个数是 0。
读 A[0] = 2 · 记入 A 侧：指针挪到下标 0,读到 A 这一位是 2。把 2 记进 A 的已见集合,登记表里它这一行亮起来。此刻 2 还只在 A 露过面,先挂在 A 侧,等 B 那边也遇到它才算公共。
读 B[0] = 4 · 记入 B 侧：同一步再看 B 的第 0 位,读到的是 4。把 4 记进 B 的已见集合。它现在还只在 B 侧,A 那边还没碰到过它,暂时不算公共,公共个数仍是 0。
结算 · C[0] = 0：这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 0 个,对应到数组 A 上就是 0 个绿格。所以 C[0] 填 0。从初始公共个数 0 来看,这一步还没抓到公共数。
读 A[1] = 4 · 记入 A 侧：指针挪到下标 1,读到 A 这一位是 4。把 4 记进 A 的已见集合,登记表里它这一行亮起来。注意 4 之前已经在 B 侧出现过,这一记就把它升级成 A·B 公共了。
读 B[1] = 2 · 记入 B 侧：同一步再看 B 的第 1 位,读到的是 2。把 2 记进 B 的已见集合。而 2 之前 A 侧已经登记过,两边都齐了,2 当场升级成公共,公共个数涨到 2。
结算 · C[1] = 2：这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 2 个,对应到数组 A 上就是 2 个绿格。所以 C[1] 填 2。比上一位多了 2 个,公共集合又长大了。
读 A[2] = 1 · 记入 A 侧：指针挪到下标 2,读到 A 这一位是 1。把 1 记进 A 的已见集合,登记表里它这一行亮起来。此刻 1 还只在 A 露过面,先挂在 A 侧,等 B 那边也遇到它才算公共。
读 B[2] = 5 · 记入 B 侧：同一步再看 B 的第 2 位,读到的是 5。把 5 记进 B 的已见集合。它现在还只在 B 侧,A 那边还没碰到过它,暂时不算公共,公共个数仍是 2。
结算 · C[2] = 2：这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 2 个,对应到数组 A 上就是 2 个绿格。所以 C[2] 填 2。和上一位持平,说明这一步没抓到新的公共数。
读 A[3] = 5 · 记入 A 侧：指针挪到下标 3,读到 A 这一位是 5。把 5 记进 A 的已见集合,登记表里它这一行亮起来。注意 5 之前已经在 B 侧出现过,这一记就把它升级成 A·B 公共了。
读 B[3] = 1 · 记入 B 侧：同一步再看 B 的第 3 位,读到的是 1。把 1 记进 B 的已见集合。而 1 之前 A 侧已经登记过,两边都齐了,1 当场升级成公共,公共个数涨到 4。
结算 · C[3] = 4：这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 4 个,对应到数组 A 上就是 4 个绿格。所以 C[3] 填 4。比上一位多了 2 个,公共集合又长大了。这一轮 A 补上了 B 侧的 5,B 又补上了 A 侧的 1,所以公共数一次涨了 2 个。
读 A[4] = 3 · 记入 A 侧：指针挪到下标 4,读到 A 这一位是 3。把 3 记进 A 的已见集合,登记表里它这一行亮起来。此刻 3 还只在 A 露过面,先挂在 A 侧,等 B 那边也遇到它才算公共。
读 B[4] = 6 · 记入 B 侧：同一步再看 B 的第 4 位,读到的是 6。把 6 记进 B 的已见集合。它现在还只在 B 侧,A 那边还没碰到过它,暂时不算公共,公共个数仍是 4。
结算 · C[4] = 4：这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 4 个,对应到数组 A 上就是 4 个绿格。所以 C[4] 填 4。和上一位持平,说明这一步没抓到新的公共数。
读 A[5] = 6 · 记入 A 侧：指针挪到下标 5,读到 A 这一位是 6。把 6 记进 A 的已见集合,登记表里它这一行亮起来。注意 6 之前已经在 B 侧出现过,这一记就把它升级成 A·B 公共了。
读 B[5] = 3 · 记入 B 侧：同一步再看 B 的第 5 位,读到的是 3。把 3 记进 B 的已见集合。而 3 之前 A 侧已经登记过,两边都齐了,3 当场升级成公共,公共个数涨到 6。
结算 · C[5] = 6：这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 6 个,对应到数组 A 上就是 6 个绿格。所以 C[5] 填 6。比上一位多了 2 个,公共集合又长大了。
回放 · C = [0, 2, 2, 4, 4, 6]：六位全部扫完。整条 A 都变绿了,因为到最后 A 和 B 见过的数字完全一样,六个数全是公共数。回看这张 C 等于 0、2、2、4、4、6,它自始至终不下降:每读一位,已见集合只增不减,公共数只会持平或变多,绝不会往回掉。这就是这道题最核心的规律。
边界想清:单元素两边同值记 1、错位排列到读完才凑齐、两数组相同则 C 逐位加一。
面试重点:双集合边扫边求交集、位掩码可优化到 O(n)、排列性质保证计数取最小值即公共。
参考代码
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 findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]: ans = [] cnt1 = Counter() cnt2 = Counter() for a, b in zip(A, B): cnt1[a] += 1 cnt2[b] += 1 t = sum(min(v, cnt2[x]) for x, v in cnt1.items()) ans.append(t) return ans复杂度
- 时间：O(n²)，参考代码外层扫 n 位,每一位再从 1 到 n 把两个计数数组的较小值累加一遍,是一层套一层,共约 n 乘 n 次操作。用位掩码或哈希维护交集可优化到 O(n),但常数与思路更绕
- 空间：O(n)，两个长度 n 加 1 的计数数组(或两个 Counter),外加长度 n 的答案数组。都随 n 线性增长,不额外开二维结构
易错点
面试追问把动画讲成自己的话
追问这题最直接的思路是什么?
追问怎么把复杂度做到 O(n)?
追问为什么用计数数组也能正确统计?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
单词搜索 II
LeetCode 212 · 困难 · 沿着 字典树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题