How does the array scanning approach work in this problem?

Array scanning helps you evaluate each index in both arrays, incrementally counting common elements. This approach ensures the solution is efficient and avoids unnecessary rechecking of elements.

What is the time complexity of the solution?

The time complexity of the solution is O(n), where n is the length of the input arrays. This is due to the single pass over the arrays and constant-time hash table lookups.

Why is using a hash table important in this problem?

A hash table is crucial for efficiently tracking the frequency of numbers in both arrays, allowing for constant time lookups and avoiding repeated iterations over the arrays.

Can this solution be optimized for larger arrays?

For very large arrays, optimizing space and time complexity can involve early termination or other advanced techniques, but for arrays of size n <= 50, this solution is efficient.

What are some common pitfalls in solving this problem?

Common pitfalls include failing to track the frequency of numbers correctly, overcomplicating the solution with unnecessary nested loops, or ignoring the problem's constraints.

#2657

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找到两个数组的前缀公共数组

给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。 A 和 B 的前缀公共数组定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。请你返回 A 和 B 的前缀公共数组。如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数…

数组哈希表位运算

题目描述

给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。

A 和 B 的 前缀公共数组 定义为数组 C ，其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。

请你返回 A 和 B 的 前缀公共数组 。

如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次，我们称这个数组是一个长度为 n 的排列。

示例 1：

输入：A = [1,3,2,4], B = [3,1,2,4]
输出：[0,2,3,4]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：1 和 3 是两个数组的前缀公共元素，所以 C[1] = 2 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。
i = 3：1，2，3 和 4 是两个数组的前缀公共元素，所以 C[3] = 4 。

示例 2：

输入：A = [2,3,1], B = [3,1,2]
输出：[0,1,3]
解释：i = 0：没有公共元素，所以 C[0] = 0 。
i = 1：只有 3 是公共元素，所以 C[1] = 1 。
i = 2：1，2 和 3 是两个数组的前缀公共元素，所以 C[2] = 3 。

提示：

1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
题目保证 A 和 B 两个数组都是 n 个元素的排列。

lightbulb

解题思路

方法一：计数

我们可以使用两个数组 $cnt1$ 和 $cnt2$ 分别记录数组 $A$ 和 $B$ 中每个元素出现的次数，用数组 $ans$ 记录答案。

遍历数组 $A$ 和 $B$ ，将 $A[i]$ 在 $cnt1$ 中出现次数加一，将 $B[i]$ 在 $cnt2$ 中出现次数加一。然后枚举 $j \in [1,n]$ ，计算 $cnt1$ 和 $cnt2$ 中每个元素 $j$ 出现次数的最小值，累加到 $ans[i]$ 中。

遍历结束后，返回答案数组 $ans$ 即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $A$ 和 $B$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of array scanning and hash lookup.
question_mark
The candidate considers the importance of efficient tracking using a frequency array.
question_mark
The candidate proposes an optimal solution with clear handling of edge cases.

warning

常见陷阱

外企场景

error
Failing to properly track the frequency of numbers in both arrays, leading to incorrect results.
error
Overcomplicating the solution with nested loops instead of using efficient hash lookups.
error
Not considering the constraints and trying to use less efficient approaches with higher time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the arrays were not permutations and contained duplicates? How would the approach change?
arrow_right_alt
Can the algorithm be optimized further for larger array sizes? Consider techniques like early termination.
arrow_right_alt
What if the problem were extended to find common prefixes for more than two arrays?

help

常见问题

外企场景

继续练习

#2588 统计美丽子数组数目 #2732 找到矩阵中的好子集 #2564 子字符串异或查询