这道题在题单里的编号是“E.位运算-基础”但真正上手做过的人都知道如果你只盯着位运算三个字去硬套反而容易把简单问题想复杂。题目本身是LeetCode 2657找两个数组的前缀公共数组输入是两个0到n-1的排列要求输出一个数组C其中C[i]表示A[0..i]和B[0..i]这两个前缀区间里公共元素的个数。整道题的核心既不是位运算炫技也不是什么高深的数据结构而是你能不能把“前缀”和“公共”这两个词拆明白。这篇文章适合刚刷数组题的新手也适合准备面试想短时间过一遍常见解法的朋友。我会从暴力做法一路讲到计数数组、位掩码再顺着热词把树状数组、指针数组、数组去重这些边角料一并盘一盘帮你把这道题上下游的知识点全部串起来。1. 先把题意嚼碎前缀公共数组到底在算什么1.1 题目限制条件里的关键信号LeetCode 2657有个非常特殊的限制A和B都是0到n-1的一个排列。这句话是什么意思意思是A和B的长度都是n里面的数字正好是0、1、2、……、n-1各出现一次没有重复也没有缺失。这个条件太重要了它直接决定了后面所有解法的可行性。如果题目去掉这句改成任意数组、允许重复那很多“优雅”的写法立刻失效你必须退回到更通用的哈希表方案。所以刷题第一步永远是读限制别急着上手写代码。题目要输出的C[i]不是让你输出公共元素本身而是输出个数。举个例子A [1, 3, 2, 0]B [0, 1, 3, 2]i0时A前缀是[1]B前缀是[0]没有任何相同元素C[0]0。i1时A前缀是[1,3]B前缀是[0,1]公共元素只有1C[1]1。i2时A前缀是[1,3,2]B前缀是[0,1,3]公共元素有1和3C[2]2。i3时两个完整数组都是0到3的排列所以公共元素有4个C[3]4。注意C数组是单调不减的因为前缀在不断变长两个前缀的交集只会变大或不变绝不会变小。利用这个性质可以省掉很多不必要的判断。1.2 最容易踩的坑公共元素按值算不按下标算很多人第一次看这题会下意识以为“公共”是指两个数组在同一位置的元素相等也就是A[i] B[i]。这是完全错误的。题目说的是“present in both prefixes”意思是只要这个值在前缀A里出现过、也在前缀B里出现过就算公共跟它在哪一位出现完全无关。出现这个误解的原因是把这题和“同位相等计数”的题目混了。判断A[i] B[i]的题目通常叫“对应位置相等”或“逐位比较”而这题的“公共”是集合意义的交集。想通了这一点后续所有解法都会围绕“维护两个前缀中出现过的数字集合”展开而不是围绕“下标联动”。1.3 暴力解法先能跑通再谈优化最不用动脑子的做法是对于每个i把A[0..i]的所有元素丢进一个临时集合再把B[0..i]的所有元素丢进另一个临时集合然后遍历其中一个集合统计另一个集合里也有多少元素。时间复杂度是O(n^2)因为每个前缀i都要重新扫描i1个元素总操作次数是123...n n(n1)/2。用C写大概是这个感觉vectorint findThePrefixCommonArray(vectorint A, vectorint B) { int n A.size(); vectorint C(n); for (int i 0; i n; i) { unordered_setint sa, sb; for (int j 0; j i; j) { sa.insert(A[j]); sb.insert(B[j]); } int cnt 0; for (int x : sa) { if (sb.count(x)) cnt; } C[i] cnt; } return C; }这个代码能通过示例但在真正的大数据范围下会超时。它最大的问题不是用了集合而是每次i都从头开始重建集合完全浪费了“前缀是逐步增长”这个事实。我们完全可以一边遍历一边维护没必要在每一步都重算一遍历史。2. 最朴素的优化思路增量维护出现次数2.1 把“重新计算”改成“增量更新”既然前缀是逐步扩展的那么从i-1到i这一步实际上只多了两个新元素A[i]和B[i]。其他所有元素在上一步都已经处理过了。所以我们要做的不是重新统计一遍全集而是考虑这两个新元素的加入会不会让公共计数发生变化。怎么判断变化想象有两个盒子一个装A前缀出现过的数字一个装B前缀出现过的数字。一个新数字A[i]如果已经在B前缀里出现过那它就成为了新的公共元素同理B[i]如果已经在A前缀里出现过也成为了新的公共元素。但这里有个细节要小心如果A[i]和B[i]是同一个数字并且这个数字之前没在双方都出现过那么它只能计一次不能重复计数。2.2 用一个cnt数组同时统计两边的出现情况最经典的做法是开一个长度n的计数数组cntcnt[x]表示数字x到目前为止同时被两个前缀覆盖的状态。具体逻辑是每次遍历i时分别对A[i]和B[i]把cnt加一然后检查加完之后的值是否等于2。如果一个数字的cnt从1变成2说明它第一次在两个前缀中都出现了公共计数加一。vectorint findThePrefixCommonArray(vectorint A, vectorint B) { int n A.size(); vectorint C(n); vectorint cnt(n, 0); int common 0; for (int i 0; i n; i) { cnt[A[i]]; if (cnt[A[i]] 2) common; cnt[B[i]]; if (cnt[B[i]] 2) common; C[i] common; } return C; }这段代码就是整道题的“标准答案”之一时间O(n)空间O(n)。它的精髓在于把集合交集的统计转化成了“每个数字出现次数的阈值判断”。因为A和B是排列每个数字整体最多出现两次A里一次B里一次所以cnt[x]达到2就必然表示同时出现在两个前缀中。2.3 为什么cnt[x] 2这个信号是可靠的这里需要再往深想一层。如果题目不是排列比如数组里有重复元素cnt[x]达到2并不能说明它在两个前缀里都出现过可能是同一个数组里出现了两次。那这个解法就得加额外判断——比如分别统计A侧出现和B侧出现而不是合并成一个计数器。但本题因为排列限制A内部不会有重复B内部也不会有重复所以数字x最多只可能因为A[i]加一次、B[i]加一次而变成2这个2一定代表“两边都见过”。这也是为什么我说读题时的排列限制是解题的钥匙它直接保障了cnt数组方案的语义正确性。我在实际写这道题的时候首选方案就是cnt数组不是位运算。它的通用性最好、代码最不容易翻车而且变量名直观面试时讲给面试官听对方三秒就能跟上思路。3. 位运算解法用二进制位表示数字的出现状态3.1 位运算为什么能插一脚既然A和B是0到n-1的排列每个数字恰好出现一次那么“一个前缀里出现了哪些数字”就可以用一段二进制串来表示第x位是1表示数字x出现过是0表示没出现过。比如数字集合{0, 3, 5}在8位二进制里就是00101001从低位到高位依次对应0到7。两个前缀的公共元素就是两个二进制掩码按位与之后仍然为1的那些位。公共元素的个数就等于按位与结果里1的个数。这样我们就不需要cnt数组了只需要两个位掩码maskA和maskB每步更新A[i]和B[i]对应的位然后统计(maskA maskB)中1的数量。3.2 用C实现时要小心的溢出问题C里一个int只有32位long long只有64位。如果n比较小比如n 30可以塞进intn 60可以用long long但LeetCode原题的n上限通常是100一个64位整数不够装下100个位。这时候有两种选择一是用两个uint64_t拼接二是直接用std::bitset100。很多新手在这里翻车用1 x处理x40就直接溢出了得到的结果完全错误。正确写法是1ULL x确保用无符号64位整数来移位。以下是n 100时用两个64位整数的写法vectorint findThePrefixCommonArray(vectorint A, vectorint B) { int n A.size(); vectorint C(n); unsigned long long maskA1 0, maskA2 0; // 分别表示0-63和64-99 unsigned long long maskB1 0, maskB2 0; for (int i 0; i n; i) { if (A[i] 64) maskA1 | (1ULL A[i]); else maskA2 | (1ULL (A[i] - 64)); if (B[i] 64) maskB1 | (1ULL B[i]); else maskB2 | (1ULL (B[i] - 64)); C[i] __builtin_popcountll(maskA1 maskB1) __builtin_popcountll(maskA2 maskB2); } return C; }如果嫌两个64位拼接麻烦可以直接用std::bitsetvectorint findThePrefixCommonArray(vectorint A, vectorint B) { int n A.size(); vectorint C(n); bitset100 maskA, maskB; for (int i 0; i n; i) { maskA.set(A[i]); maskB.set(B[i]); C[i] (maskA maskB).count(); } return C; }bitset版本在n已知且不大时代码简洁得多可读性也更好。它的内部实现本来就是把多个64位整数拼在一起所以性能并不差。3.3 按位或赋值运算 | 的语义要理解透热词里有“按位或赋值运算”正好对应到这里。maskA | (1ULL A[i])的意思是把maskA的第A[i]个二进制位设为1同时不影响其他位。按位或的性质是只要两个操作数里有一个在某一位置为1结果的那一位就是1。所以它非常适合“把某个数字标记为出现过”这个场景。如果你用异或赋值^就不对了。异或的结果是相同为0、不同为1同一个数字如果出现两次就会把自己抵消掉。虽然排列限制下A内部不会重复但同一个数字在A和B里各出现一次如果混用掩码或操作不当会把位翻回去。按位与在这里的作用是求交集只有两边都为1的位结果才是1。这正好对应“数字在两个前缀里都出现过”的语义。所以__builtin_popcountll(maskA maskB)就是在数交集大小本质上和cnt数组里“公共计数”是一回事。3.4 位运算解法的边界在哪里位运算方案看着很帅但它有个硬前提每个数字最多出现一次且值域最好不超过机器字长或bitset上限。如果第一点不满足比如数组变成[1,1,2,3]这种位运算里一个1的位只表示“出现过”无法处理重复出现对计数的影响。如果第二点不满足比如值域到10^9你总不能开一个10^9位的bitset。所以我的建议是位运算解法看一遍、写一遍、理解里面的位操作就够了真正笔试或面试时优先写cnt数组方案。位运算方案更适合用来展示你懂位掩码、懂二进制操作但在工程上它脆得很。真遇到n10^5、值域10^9的场景别说位掩码cnt数组都得先压缩坐标再上。4. 热词延伸这些数组相关概念到底和这题搭不搭4.1 指针数组、二维数组、数组指针这些概念跟本题无关热词列表里有大量C/C的数组概念比如指针数组、数组指针、二维字符数组、字符串数组初始化之类。这些确实是C/C学习者经常搜的内容但坦白说做LeetCode 2657这道题用不上指针数组也用不上二维数组。题目给的是两个一维整型vector操作就是按下标访问不涉及指针的复杂运算。如果你在搜索过程中看到这些概念觉得心虚我建议单独花点时间把“数组指针”和“指针数组”区分清楚。指针数组是“数组里存的是指针”数组指针是“指向整个数组的指针”比如int (*p)[10]。这种基础概念逃不掉但不要把它们的复习混入这道题的解题过程否则容易分散注意力。一道题就干一件事刷题最忌讳在一道简单题里想着把所有知识点都塞进去。4.2 树状数组能不能解这道题热词里有“树状数组维护前缀和 sum(11) 与单点修改 add(3, x)”还有人问这题能不能用树状数组。我的回答是能但没必要。树状数组解决的是“单点修改、区间前缀查询”的问题通常用于动态数据场景且查询的是某种可合并的统计量比如和、最大值。在这道题里如果硬要用树状数组思路是维护一个数组tree遍历i时对A[i]和B[i]做单点加一然后查询前缀区间[0, n-1]里等于2的数字个数。但这里有个困难——树状数组查询区间和只能告诉你“总数”无法直接告诉你“有多少个位置等于2”。你需要在每次更新后重新遍历整个数组来数有多少个2那树状数组就失去了意义。真正要用树状数组处理“前缀公共元素个数”的变体题一般是把问题拆成离线比如给很多次区间查询问两个区间的交集大小这时候可以用树状数组维护每个数字最后一次出现位置之类的技巧。但那是另一道题了不是这道题该考虑的事。这道题每个i都是即时查询整个前缀cnt数组已经是最优解再往上套树状数组属于大炮打蚊子。4.3 数组排序、数组去重、数组切片这些热词说明什么热词里出现“js数组排序的几种方法”、“数组去重”、“python数组切片”、“es6提取数组对象一部分”说明很多搜这道题的人其实还在学数组基础。这很正常LeetCode 2657的难度定位就是基础题适合刚接触编程不久的人。但我得提醒一句这题不需要先排序也不需要去重更不需要切片。排序会破坏原始下标对应的前缀语义去重在这里是多余的因为排列本身没有重复Python切片虽然可以写出类似A[:i1]的代码来计算前缀但切片会复制数组时间复杂度变成O(n^2)在面试中反而扣分。正确的做法是像前面那样一次遍历、不断更新状态根本不需要把前缀切片拿出来反复操作。Python版如果非要用集合写可以参考这个class Solution: def findThePrefixCommonArray(self, A: List[int], B: List[int]) - List[int]: n len(A) cnt [0] * n C [0] * n common 0 for i in range(n): cnt[A[i]] 1 if cnt[A[i]] 2: common 1 cnt[B[i]] 1 if cnt[B[i]] 2: common 1 C[i] common return CPython里用列表当计数数组语义和C的vector 完全一致。不需要用字典因为值域固定是0到n-1列表下标直接映射数字比哈希表更快。4.4 其他语言写这题的思路大同小异热词里还出现了Java、C#、PHP、VBA、MATLAB等语言的数组问题本质上都是围绕“数组创建、数组遍历、数组元素判断”展开。拿这道题来说Java用int[]C#用int[]PHP用arrayMATLAB用向量JS用Array大家的核心算法逻辑完全一样区别只在语法层面。我见过有人用PHP的关联数组当哈希表来写其实没必要。只要值域连续就开一个普通数组当计数器。PHP里你可以直接$cnt[$A[$i]]PHP的普通数组本身就是有序映射用起来反而更像哈希。但需要注意PHP数组下标不会自动补0你需要先初始化或者给默认值否则Notice警告会刷屏。VBA和Excel在这个话题里属于“办公室里莫名奇妙出现的热搜词”。如果真的有人在Excel里想算“两个区间前缀的公共元素个数”那通常不是用数组公式硬算而是要借助辅助列。但这不是LeetCode题解该讨论的范围了我只能说算法思路可以迁移工程实现完全两码事。5. 复杂度剖析与解题方案的横向对比5.1 三种解法的时空复杂度对照暴力解法时间O(n^2)、空间O(n)存结果C数组。cnt数组解法时间O(n)、空间O(n)。位运算解法时间O(n)、空间O(1)或O(n/64)取决于用普通整数还是bitset。这里强调一点无论是哪种解法都要把结果数组C的空间算进去因为题目要求返回它这部分是不可避免的。解法时间复杂度空间复杂度是否依赖排列限制代码量推荐指数暴力集合O(n^2)O(n)不依赖少不推荐cnt计数数组O(n)O(n)依赖可改造很少强烈推荐位掩码O(n)O(1)或O(n/64)强依赖少视场景bitsetO(n)O(n/8)强依赖最少推荐5.2 空间优化到底有没有必要有人会问cnt数组能不能优化成O(1)空间理论上你仍然需要记录每个数字在两边的出现状态这个信息量本身就是O(n)的所以不可能压到O(1)。除非你允许修改原数组比如把A[i]对应位置的元素取反作为标记但那样会破坏输入数据在LeetCode和面试场景都不被允许。5.3 位运算解法的常数优势实际有多大现代CPU对位运算的支持非常快__builtin_popcountll在硬件上可能只需要一条指令而cnt数组方案虽然也是O(n)但每次循环要做两次数组访问和两次条件分支。当n非常小的时候位运算方案可能确实快那么一点点但差异在毫秒级别根本感知不到。如果你只是为了刷题不用纠结这点性能差。真正决定你该选哪个方案的是代码的可读性和扩展性。面试官更愿意听你讲cnt数组的“增量维护”思想因为它能很自然地延伸到其他数组题比如“最长公共前缀”、“滑动窗口计数”等。6. 做题过程中的典型翻车现场与问题排查6.1 C左移溢出最隐蔽的错误我第一次写位运算版本时直接写了1 A[i]当A[i]等于40的时候出现负数掩码错乱。后来查了半天才反应过来int只有32位左移超过31位就是未定义行为。改成1ULL A[i]后问题消失。如果你用bitset就不会遇到这个坑因为bitset内部会自动管理。所以我的建议是能用bitset就用bitset别手搓两个uint64_t。手搓代码看着很专业但每一行都要小心边界很容易在A[i] 64的分支里忘记减偏移量。6.2 数组下标越界n很小但值域很大的错觉还有一种错误是看到题目说A和B是排列就默认值域一定小于n于是开了vector cnt(n)。这没问题。但如果输入的测试用例里出现了一个超出范围的值就会下标越界。刷题平台一般会保证数据合法性但如果你自己写测试用例一定要清楚限制只有排列cnt数组大小才敢开n。假如题目改成普通数组值域可能达到10^9就得改用哈希表来计数。6.3 重复计数问题A[i]和B[i]相等时只应计一次再回到cnt数组的代码如果A[i]和B[i]恰好相等比如两个都是5那么第一段if (cnt[A[i]] 2) common会把common加一第二段if (cnt[B[i]] 2) common又判断一次。如果5的cnt之前是0执行完cnt[5]变成1不触发再执行cnt[5]变成2触发一次总共只加一正确。如果5的cnt之前已经是1说明5在之前已经同时出现在两个前缀中这一步两个操作都会触发吗让我们模拟一下cnt[5]原本是1。执行cnt[A[i]]cnt[5]变2触发common。执行cnt[B[i]]cnt[5]变3不触发等于3不等于2。所以总共还是只加一。这个逻辑实际上保证了哪怕同一个数字在同一轮里被处理两次也不会重复计数。这个细节最好自己手推一遍就能彻底避免困惑。6.4 一个完整的本地运行与调试流程如果你在本地练习可以这样搭一个最小验证环境#include bits/stdc.h using namespace std; vectorint findThePrefixCommonArray(vectorint A, vectorint B) { int n A.size(); vectorint C(n); vectorint cnt(n, 0); int common 0; for (int i 0; i n; i) { cnt[A[i]]; if (cnt[A[i]] 2) common; cnt[B[i]]; if (cnt[B[i]] 2) common; C[i] common; } return C; } int main() { vectorint A {1, 3, 2, 0}; vectorint B {0, 1, 3, 2}; auto res findThePrefixCommonArray(A, B); for (int x : res) cout x ; // 期望输出 0 1 2 4 return 0; }如果你跑出来的不是0 1 2 4那说明某个位置的cnt更新或者common递增时机出了错。排查顺序是先打印每一轮的A[i]、B[i]、cnt数组状态再检查common的递增是否发生在恰好的时机。6.5 常见问题速查表现象可能原因解决办法位运算结果出现大负数int左移溢出使用1ULL x或bitset输出数组整体比预期小忘记把cnt[B[i]]的更新条件算进去检查两个if是否都写了输出数组比预期大重复计数检查A[i]B[i]时是否只加一次本地正确但OJ超时用了切片或每次重建集合改成增量cnt数组方案未定义错误/段错误cnt数组开小了排列时开n否则开值域或哈希7. 从这道题延伸出去的几条进阶思考线7.1 如果题目改成求公共元素集合怎么办如果输出从“个数”变成“集合”cnt数组方案就吃亏了因为它记录了计数状态但没有把当前集合完整保留下来。这时候位运算方案反而更有优势因为maskA maskB的结果直接就代表了公共元素集合的位掩码你遍历一遍二进制位就能还原出所有公共值。但工程上更通用的做法是维护两个unordered_set每次计算交集。时间复杂度会增加但语义非常清楚。做题时先看清楚题目要什么再决定用哪一套体系。7.2 如果两个数组不是排列、有重复怎么办把题目的排列限制去掉变成普通数组问题难度立刻上升一档。因为重复元素会干扰“公共”的定义——比如A里有两个3、B里有一个3公共元素算3还是算6不同题目定义可能不同有的是多重集合交集按较小次数计算有的是普通集合交集看是否出现。如果是“集合并集交集式”的定义cnt数组方案必须拆成两个独立的计数状态用两个布尔数组分别记录A和B是否出现过某个值然后统计两边都为真的数量。这个扩展方向非常值得练手很多面试题都是把基础题的某个限制去掉再考。7.3 如果题目变成动态更新该怎么办假如题目不是一次性给定两个数组而是不断给A或B的某个位置插入、删除新值每次都问当前前缀公共元素个数那答案就是“老老实实用树状数组或线段树”。一面维护每个数字的位置信息一面做区间统计。思路是把每个数字想象成一个点数字x在A中出现的位置记为posA[x]在B中出现的位置记为posB[x]那么在当前前缀长度i下x是公共元素的充要条件是posA[x] i posB[x] i。所有满足这个条件的x的个数就是C[i]。这么一转换就会发现问题变成了“统计有多少个点满足两个坐标都不超过i”可以用二维偏序或树状数组离线处理。但这种题已经不是LeetCode 2657了而是另一道编程竞赛题。我只是想说明基础题的解法永远不会白学它后面能长出一串进阶问题。8. 我个人的一些实操建议这道题让我最感叹的地方是同一个问题从暴力到cnt数组到位运算三种写法的代码量差不多但思维的抽象层级完全不同。暴力是“我每次问一次就算一次”cnt数组是“我一边走一边记录状态”位运算是“我把状态压缩进一个数字里”。如果你现在刚开始刷题我建议把cnt数组方案练到能闭着眼写出来然后理解它和位运算方案之间的等价性。两个方案一个用整数数组计数一个用二进制位表示“是否出现”本质上都在维护一个随下标i不断更新的状态向量。特别是当你以后遇到“前缀状态”类问题比如前缀和、前缀最大值、前缀异或和你都会回来感谢这种“增量维护”的思维。最后分享一个小技巧遇到“前缀公共XX”的题目先别急着想数据结构先画一条时间线标出每个新加入的元素想清楚它会让状态发生什么变化。状态更新规则一旦明确代码就是水到渠成的事了。这道题的状态规则只有一句话某个数字同时被两个前缀收录时计数加一。就这么简单。