找到两个数组的前缀公共数组 图解题解

这道题到底在问什么

输入

A=[1,3,2,4], B=[3,1,2,4]

输出

[0,2,3,4]

输入

A=[2,3,1], B=[3,1,2]

输出

[0,1,3]

最优解：一步一步想明白

1. 3记牢这一句:一边扫一边往两个已见集合里登记,谁两边都露过面,谁就是公共数,当前公共数的个数就是 C[i]。因为是排列,每个数最多出现一次,判断非常干净。下面从下标 0 开始扫。
2. 4这是数组 A,紫色指针待会儿会从最左边一格一格往右挪。右边这张登记表现在是空的,它记录每个数字目前落在哪一侧:只在 A 出现记 A 侧,只在 B 出现记 B 侧,两边都出现就升级成 A·B 公共。C[i] 就是表里公共那类有几个。开局两个集合都空,公共个数是 0。
3. 5指针挪到下标 0,读到 A 这一位是 2。把 2 记进 A 的已见集合,登记表里它这一行亮起来。此刻 2 还只在 A 露过面,先挂在 A 侧,等 B 那边也遇到它才算公共。
4. 6同一步再看 B 的第 0 位,读到的是 4。把 4 记进 B 的已见集合。它现在还只在 B 侧,A 那边还没碰到过它,暂时不算公共,公共个数仍是 0。
5. 7这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 0 个,对应到数组 A 上就是 0 个绿格。所以 C[0] 填 0。从初始公共个数 0 来看,这一步还没抓到公共数。
6. 8指针挪到下标 1,读到 A 这一位是 4。把 4 记进 A 的已见集合,登记表里它这一行亮起来。注意 4 之前已经在 B 侧出现过,这一记就把它升级成 A·B 公共了。
7. 9同一步再看 B 的第 1 位,读到的是 2。把 2 记进 B 的已见集合。而 2 之前 A 侧已经登记过,两边都齐了,2 当场升级成公共,公共个数涨到 2。
8. 10这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 2 个,对应到数组 A 上就是 2 个绿格。所以 C[1] 填 2。比上一位多了 2 个,公共集合又长大了。
9. 11指针挪到下标 2,读到 A 这一位是 1。把 1 记进 A 的已见集合,登记表里它这一行亮起来。此刻 1 还只在 A 露过面,先挂在 A 侧,等 B 那边也遇到它才算公共。
10. 12同一步再看 B 的第 2 位,读到的是 5。把 5 记进 B 的已见集合。它现在还只在 B 侧,A 那边还没碰到过它,暂时不算公共,公共个数仍是 2。
11. 13这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 2 个,对应到数组 A 上就是 2 个绿格。所以 C[2] 填 2。和上一位持平,说明这一步没抓到新的公共数。
12. 14指针挪到下标 3,读到 A 这一位是 5。把 5 记进 A 的已见集合,登记表里它这一行亮起来。注意 5 之前已经在 B 侧出现过,这一记就把它升级成 A·B 公共了。
13. 15同一步再看 B 的第 3 位,读到的是 1。把 1 记进 B 的已见集合。而 1 之前 A 侧已经登记过,两边都齐了,1 当场升级成公共,公共个数涨到 4。
14. 16这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 4 个,对应到数组 A 上就是 4 个绿格。所以 C[3] 填 4。比上一位多了 2 个,公共集合又长大了。这一轮 A 补上了 B 侧的 5,B 又补上了 A 侧的 1,所以公共数一次涨了 2 个。
15. 17指针挪到下标 4,读到 A 这一位是 3。把 3 记进 A 的已见集合,登记表里它这一行亮起来。此刻 3 还只在 A 露过面,先挂在 A 侧,等 B 那边也遇到它才算公共。
16. 18同一步再看 B 的第 4 位,读到的是 6。把 6 记进 B 的已见集合。它现在还只在 B 侧,A 那边还没碰到过它,暂时不算公共,公共个数仍是 4。
17. 19这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 4 个,对应到数组 A 上就是 4 个绿格。所以 C[4] 填 4。和上一位持平,说明这一步没抓到新的公共数。
18. 20指针挪到下标 5,读到 A 这一位是 6。把 6 记进 A 的已见集合,登记表里它这一行亮起来。注意 6 之前已经在 B 侧出现过,这一记就把它升级成 A·B 公共了。
19. 21同一步再看 B 的第 5 位,读到的是 3。把 3 记进 B 的已见集合。而 3 之前 A 侧已经登记过,两边都齐了,3 当场升级成公共,公共个数涨到 6。
20. 22这一步结算。数一数登记表里标着 A·B 公共的有几个,就是 6 个,对应到数组 A 上就是 6 个绿格。所以 C[5] 填 6。比上一位多了 2 个,公共集合又长大了。
21. 23六位全部扫完。整条 A 都变绿了,因为到最后 A 和 B 见过的数字完全一样,六个数全是公共数。回看这张 C 等于 0、2、2、4、4、6,它自始至终不下降:每读一位,已见集合只增不减,公共数只会持平或变多,绝不会往回掉。这就是这道题最核心的规律。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> ans(n);
        vector<int> cnt1(n + 1), cnt2(n + 1);
        for (int i = 0; i < n; ++i) {
            ++cnt1[A[i]];
            ++cnt2[B[i]];
            for (int j = 1; j <= n; ++j) {
                ans[i] += min(cnt1[j], cnt2[j]);
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int[] findThePrefixCommonArray(int[] A, int[] B) {
        int n = A.length;
        int[] ans = new int[n];
        int[] cnt1 = new int[n + 1];
        int[] cnt2 = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            ++cnt1[A[i]];
            ++cnt2[B[i]];
            for (int j = 1; j <= n; ++j) {
                ans[i] += Math.min(cnt1[j], cnt2[j]);
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问