2657. 找到两个数组的前缀公共数组 | 难度：中等

2657. 找到两个数组的前缀公共数组 | 难度：中等

题意理解（用样例说话）

题目给定两个排列A 和 B（长度都是 n，包含 1 到 n 的每个数字恰好一次），要求我们计算「前缀公共数组」C。

关键定义：C[i] 表示在 A 和 B 的前 i+1 个元素中（即下标 0 到 i），同时出现在两个数组前缀中的不同元素个数。

用题目示例A = [1, 3, 2, 4], B = [3, 1, 2, 4]演示：

输出：[0, 2, 3, 4]

解法思路

核心观察

由于 A 和 B 都是排列，每个数字只会出现一次。因此，当我们遍历到下标 i 时：

• 如果某个数字 x 既出现在 A[0…i] 中，又出现在 B[0…i] 中，那么 x 必然会被计入 C[i]。

直观做法：双哈希集

我们可以用两个哈希集分别记录 A 和 B 的前缀元素，然后用第三个哈希集记录它们的交集。

具体步骤：

1. 初始化三个无序集合：cntA（记录 A 的前缀元素）、cntB（记录 B 的前缀元素）、cnt（记录公共元素）
2. 遍历下标 i 从 0 到 n-1：
   • 将 A[i] 插入cntA
   • 将 B[i] 插入cntB
   • 关键：检查 A[i] 是否已经在cntB中（说明 A[i] 是公共元素）
   • 关键：检查 B[i] 是否已经在cntA中（说明 B[i] 是公共元素）
   • 如果满足，将该元素加入cnt
   • 记录cnt.size()到答案数组

为什么这个方法正确？

• 由于是排列，每个数字只会出现一次，所以我们不需要计数，只需要知道「是否出现过」
• 当我们处理下标 i 时，cntA和cntB中分别记录了 A[0…i] 和 B[0…i] 的所有元素
• 如果 A[i] 在cntB中，说明 A[i] 也出现在 B 的前缀中，因此它是公共元素
• 同理适用于 B[i]

代码实现

参考你提供的代码，我们可以这样实现（添加了详细注释）：

classSolution{public:vector<int>findThePrefixCommonArray(vector<int>&A,vector<int>&B){intn=A.size();unordered_set<int>cntA,cntB;// 分别记录 A 和 B 的前缀元素unordered_set<int>cnt;// 记录当前位置的公共元素vector<int>ans;for(inti=0;i<n;i++){// 将当前元素加入各自的前缀集合cntA.emplace(A[i]);cntB.emplace(B[i]);// 关键：检查 A[i] 是否也在 B 的前缀中出现过if(cntB.count(A[i])){cnt.emplace(A[i]);// A[i] 是公共元素}// 关键：检查 B[i] 是否也在 A 的前缀中出现过if(cntA.count(B[i])){cnt.emplace(B[i]);// B[i] 是公共元素}// 当前位置的公共元素个数ans.emplace_back(cnt.size());}returnans;}};

复杂度分析

• 时间复杂度：O(n) —— 只需遍历一次数组，每次哈希集操作平均 O(1)
• 空间复杂度：O(n) —— 三个哈希集最多各存储 n 个元素

易错点

1. 不要重复计数

由于 A 和 B 都是排列，每个数字只会出现一次。但需要注意：当A[i] == B[i]时，两个if语句都会尝试插入同一个数字到cnt中。不过由于unordered_set会自动去重，所以最终结果是正确的。

错误示例（虽然不影响结果，但逻辑冗余）：

// 如果写成这样，当 A[i] == B[i] 时会检查两次if(cntB.count(A[i]))cnt.emplace(A[i]);if(cntA.count(B[i]))cnt.emplace(B[i]);// 当 A[i]==B[i] 时，这行是多余的检查

改进写法（可选）：

if(cntB.count(A[i]))cnt.emplace(A[i]);if(A[i]!=B[i]&&cntA.count(B[i]))cnt.emplace(B[i]);// 避免重复检查

不过原代码的写法更简洁，且unordered_set::emplace对于重复元素会自动忽略，所以两种写法都可以。

2. 理解「前缀」的定义

C[i] 计算的是到下标 i 之前（包括 i）的公共元素个数。有些同学会误解为「到下标 i 之前（不包括 i）」，从而导致 off-by-one 错误。

相关题目

1. 349. 两个数组的交集—— 思路类似，都是用哈希集找公共元素
2. 350. 两个数组的交集 II—— 进阶版，需要考虑元素出现次数

希望这篇题解能帮助你理解这道题的核心思路！如果还有疑问，欢迎继续讨论 💬