企业官网建设流程全解析

• 科学计算

本篇文章以 codeforces-go 算法竞赛模板库中 LeetCode 双周赛 103 的 B 题题解 为蓝本，完整拆解「找到两个数组的前缀公共数组（Find the Prefix Common Array of Two Arrays）」这道经典位运算题目：如何用二进制数表示集合、用 AND 求交集、用 popcount 统计交集大小，并给出 Python / Java / C++ / Go 四种语言的落地实现。读完本文，你将掌握一类"集合运算转位运算"的通用技巧，以及该技巧在本仓库源码与测试框架中的真实应用方式。

题目背景：LeetCode 2657 是什么题

题目编号为 LeetCode 2657（第 103 场双周赛 B 题），仓库中对应文件位于 leetcode/biweekly/103/b/，包含题解文档README.md、Go 实现 b.go、测试文件 b_test.go 与样例数据 b.txt。

题目大意：给定两个长度为 $n$ 的排列a和b，定义ans[i]为「在a[0..i]和b[0..i]这两个前缀中都出现过的元素个数」（即两个前缀的交集大小）。要求返回数组ans。直接对每个前缀都做一次扫描的朴素做法是 $\mathcal{O}(n^2)$，而位运算技巧可以把整体复杂度降到 $\mathcal{O}(n)$。

核心思想：用二进制数表示集合

题解文档的第一句话就是全部算法的出发点：

用二进制数表示集合，两个二进制数的 AND 就是集合的交集，二进制数中 $1$ 的个数就是交集的大小。

展开来说，这是一个"集合与位掩码（bitmask）"的对应关系：

• 每个整数x（元素值）对应二进制中的第x位；
• 一个集合S用整数mask表示，mask的第x位为 1 当且仅当x ∈ S；
• 集合交集S ∩ T对应位运算p & q；
• 交集大小|S ∩ T|对应统计p & q二进制中 1 的个数（popcount，Go 中为bits.OnesCount）。

以样例a = [1,3,2,4]、b = [3,1,2,4]为例，处理到下标i = 2时，a前缀{1,3,2}对应p的第 1、3、2 位为 1，b前缀{3,1,2}对应q的第 3、1、2 位为 1，则p & q为 1 的位恰好是第 1、3、2 位，共 3 个，即ans[2] = 3。

算法流程：单趟扫描，边加入边统计

由于两个数组都是排列，且长度相同，可以一趟遍历同时处理两个前缀：

1. 初始化两个掩码p = 0、q = 0；
2. 遍历下标i，把a[i]的第a[i]位加入p：p |= 1 << a[i]；
3. 把b[i]的第b[i]位加入q：q |= 1 << b[i]；
4. 当前前缀交集大小 =popcount(p & q)，写入ans[i]。

每一步都是 $\mathcal{O}(1)$，因此整体为 $\mathcal{O}(n)$。这里有一个细节值得注意：用|=而不是=做位或赋值，因为前缀是累积的，后一个前缀包含前一个前缀的所有元素，掩码只增不减。

四种语言实现（完整对照）

原题解文档提供了 Python3、Java、C++、Go 四种语言的完整实现，这里全部保留并逐段注释。

Python3

class Solution: def findThePrefixCommonArray(self, a: List[int], b: List[int]) -> List[int]: ans = [] p = q = 0 for x, y in zip(a, b): p |= 1 << x q |= 1 << y ans.append((p & q).bit_count()) return ans

Python 3.10+ 的内置方法int.bit_count()统计二进制中 1 的个数，对应题目中的 popcount。

Java

class Solution { public int[] findThePrefixCommonArray(int[] a, int[] b) { long p = 0, q = 0; for (int i = 0; i < a.length; i++) { p |= 1L << a[i]; q |= 1L << b[i]; a[i] = Long.bitCount(p & q); } return a; } }

Java 版本有两个工程细节：一是把结果原地写回a[i]，省掉额外数组的分配；二是1L << a[i]显式使用long移位，避免int移位在 32 位边界上的溢出问题（本题数据范围在 64 位内安全）。

C++

class Solution { public: vector<int> findThePrefixCommonArray(vector<int>& a, vector<int>& b) { uint64_t p = 0, q = 0; for (int i = 0; i < a.size(); i++) { p |= 1ULL << a[i]; q |= 1ULL << b[i]; a[i] = popcount(p & q); } return a; } };

C++ 使用uint64_t与1ULL保证 64 位无符号语义，popcount是内建函数族，可在__builtin_popcountll等实现间无缝替换。

Go

func findThePrefixCommonArray(a, b []int) []int { var p, q uint for i, x := range a { p |= 1 << x q |= 1 << b[i] a[i] = bits.OnesCount(p & q) } return a }

Go 版本使用math/bits标准库的bits.OnesCount统计 1 的个数，uint类型在 64 位平台下足以容纳题目范围内的元素位。

仓库源码验证：b.go 的实现与逐行对照

仓库中的实际实现位于 leetcode/biweekly/103/b/b.go，与题解文档中的 Go 版本完全一致：

package main import "math/bits" // https://space.bilibili.com/206214 func findThePrefixCommonArray(a, b []int) []int { ans := make([]int, len(a)) var p, q uint for i, x := range a { p |= 1 << x q |= 1 << b[i] ans[i] = bits.OnesCount(p & q) } return ans }

两点实现细节可以直接从源码确认：

1. 这里显式make([]int, len(a))分配了答案数组（题解文档中的 Python 版本是追加式append，Go 采用预分配写法避免扩容开销）；
2. bits.OnesCount来自标准库math/bits，在 64 位平台下uint为 64 位，足以表示题目给出的排列范围。bits.OnesCount是该仓库位运算工具箱中的高频原语，在 copypasta/bits.go 中可以看到大量基于它的讨论（如OnesCount相当于二进制的 digsum、n+OnesCount(n)等数列恒等式），也在 copypasta/bitset.go 的Bitset.OnesCountRange等位集统计方法中被反复调用。

测试框架验证：b_test.go 与 b.txt

题目仓库配有自动化测试，验证了位运算解法的正确性。测试代码位于 leetcode/biweekly/103/b/b_test.go：

// Code generated by copypasta/template/leetcode/generator_test.go package main import ( "github.com/EndlessCheng/codeforces-go/leetcode/testutil" "testing" ) func Test_b(t *testing.T) { targetCaseNum := 0 // -1 if err := testutil.RunLeetCodeFuncWithFile(t, findThePrefixCommonArray, "b.txt", targetCaseNum); err != nil { t.Fatal(err) } if err := testutil.RunFuncWithRandomInput(t, findThePrefixCommonArray); err != nil { t.Fatal(err) } }

测试分为两条路径：

• RunLeetCodeFuncWithFile：从 b.txt 读取手工构造的样例数据逐组比对。从 leetcode/testutil/leetcode.go 的实现可以看到，该工具通过反射获取被测试函数的NumIn与NumOut，将文件中的行按"输入行数 + 输出行数"分组为测试用例，若有效行数不是组大小的倍数会直接报错，从而保证数据格式的严谨性。b.txt 中存放了两组用例：

[1,3,2,4] [3,1,2,4] [0,2,3,4] [2,3,1] [3,1,2] [0,1,3]

每组前两行是输入数组a、b，第三行是期望输出ans。对第一组：前 1 个元素时前缀交集为空，前 2 个元素交集为{1,3}大小为 2，前 3 个元素交集为{1,3,2}大小为 3，前 4 个元素交集为全集大小为 4，得到[0,2,3,4]，与文件中的期望输出一致。

• RunFuncWithRandomInput：额外用随机输入对拍，进一步覆盖边界情况。

运行方式：在仓库根目录执行go test ./leetcode/biweekly/103/b/ -run Test_b即可复现上述验证。

复杂度分析

原题解文档给出的复杂度结论如下：

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是nums的长度。每一步循环只做两次位或、一次位与和一次 popcount，均为 $\mathcal{O}(1)$；
• 空间复杂度：$\mathcal{O}(1)$（除返回值本身外，只使用了两个掩码变量）。返回值数组不计入额外空间。

相比朴素的两重循环（对每个前缀重新统计共现元素），位运算方法既压低了时间到线性，又不需要哈希表或计数数组，是竞赛解法中最简洁的一种。

延伸：位运算集合技巧在本仓库的更多应用

本题所用的"集合 ↔ 位掩码"对应关系是算法竞赛中的通用范式，本仓库 copypasta/bits.go 对这类技巧有系统化整理，包括但不限于：

• 用二进制数的 1 的个数表示集合大小（OnesCount相当于二进制的 digsum）；
• 子集枚举、状态压缩 DP 中常见的1<<s与掩码操作（见 copypasta/dp.go 中大量基于1<<s的状态转移）；
• 位集（bitset）上对一段区间统计 1 的个数（copypasta/bitset.go 的OnesCountRange）；
• 利用bits.OnesCount(3*n ^ n)等恒等式做奇偶性判断（copypasta/misc.go）。

如果你打算系统性训练位运算，可以把本题作为"二进制集合 + 交集 + popcount"三件套的入门题，再结合仓库中的位运算实现逐步深入拆位、试填等进阶技巧。

总结

LeetCode 2657「找到两个数组的前缀公共数组」表面上是一道模拟题，但用"二进制数表示集合"的视角，可以将其化为一趟线性扫描：p |= 1<<x记录a前缀，q |= 1<<y记录b前缀，bits.OnesCount(p & q)（或其语言对应物）给出交集大小。原题解文档给出了四种语言的完整可运行代码，仓库中的 b.go 与 b_test.go 则提供了可直接go test验证的实现与测试数据，是一份"从思路到代码再到验证"闭环的样例学习材料。

• 科学计算