2657. 找到两个数组的前缀公共数组 | 难度中等题意理解用样例说话题目给定两个排列A 和 B长度都是 n包含 1 到 n 的每个数字恰好一次要求我们计算「前缀公共数组」C。关键定义C[i] 表示在 A 和 B 的前 i1 个元素中即下标 0 到 i同时出现在两个数组前缀中的不同元素个数。用题目示例A [1, 3, 2, 4], B [3, 1, 2, 4]演示下标 iA 的前缀B 的前缀公共元素C[i]0[1][3]无01[1, 3][3, 1]{1, 3}22[1, 3, 2][3, 1, 2]{1, 2, 3}33[1, 3, 2, 4][3, 1, 2, 4]{1, 2, 3, 4}4输出[0, 2, 3, 4]解法思路核心观察由于 A 和 B 都是排列每个数字只会出现一次。因此当我们遍历到下标 i 时如果某个数字 x 既出现在 A[0…i] 中又出现在 B[0…i] 中那么 x 必然会被计入 C[i]。直观做法双哈希集我们可以用两个哈希集分别记录 A 和 B 的前缀元素然后用第三个哈希集记录它们的交集。具体步骤初始化三个无序集合cntA记录 A 的前缀元素、cntB记录 B 的前缀元素、cnt记录公共元素遍历下标 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:vectorintfindThePrefixCommonArray(vectorintA,vectorintB){intnA.size();unordered_setintcntA,cntB;// 分别记录 A 和 B 的前缀元素unordered_setintcnt;// 记录当前位置的公共元素vectorintans;for(inti0;in;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 错误。相关题目349. 两个数组的交集—— 思路类似都是用哈希集找公共元素350. 两个数组的交集 II—— 进阶版需要考虑元素出现次数希望这篇题解能帮助你理解这道题的核心思路如果还有疑问欢迎继续讨论
2657. 找到两个数组的前缀公共数组 | 难度：中等
2657. 找到两个数组的前缀公共数组 | 难度中等题意理解用样例说话题目给定两个排列A 和 B长度都是 n包含 1 到 n 的每个数字恰好一次要求我们计算「前缀公共数组」C。关键定义C[i] 表示在 A 和 B 的前 i1 个元素中即下标 0 到 i同时出现在两个数组前缀中的不同元素个数。用题目示例A [1, 3, 2, 4], B [3, 1, 2, 4]演示下标 iA 的前缀B 的前缀公共元素C[i]0[1][3]无01[1, 3][3, 1]{1, 3}22[1, 3, 2][3, 1, 2]{1, 2, 3}33[1, 3, 2, 4][3, 1, 2, 4]{1, 2, 3, 4}4输出[0, 2, 3, 4]解法思路核心观察由于 A 和 B 都是排列每个数字只会出现一次。因此当我们遍历到下标 i 时如果某个数字 x 既出现在 A[0…i] 中又出现在 B[0…i] 中那么 x 必然会被计入 C[i]。直观做法双哈希集我们可以用两个哈希集分别记录 A 和 B 的前缀元素然后用第三个哈希集记录它们的交集。具体步骤初始化三个无序集合cntA记录 A 的前缀元素、cntB记录 B 的前缀元素、cnt记录公共元素遍历下标 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:vectorintfindThePrefixCommonArray(vectorintA,vectorintB){intnA.size();unordered_setintcntA,cntB;// 分别记录 A 和 B 的前缀元素unordered_setintcnt;// 记录当前位置的公共元素vectorintans;for(inti0;in;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 错误。相关题目349. 两个数组的交集—— 思路类似都是用哈希集找公共元素350. 两个数组的交集 II—— 进阶版需要考虑元素出现次数希望这篇题解能帮助你理解这道题的核心思路如果还有疑问欢迎继续讨论
