最长重复子数组 图解题解

两数组的最长公共子数组，连续这两个字卡在哪

给两个整数数组 A 和 B，要在它们里各挑出一段完全相同、而且在各自数组里连着排的片段，返回这段能有多长。题面 A=[1,2,3,2,1]、B=[3,2,1,4,7]，两边都出现过又都连续的最长片段是 [3,2,1]，长度 3。难点全压在「连续」上：中间断了一格，这段就不算数，得从断点重新数起。

把每对起点都往后比一遍为什么撑不住

一个直觉做法是把 A 的每个起点、B 的每个起点两两配对，再沿着往后逐位比对能对齐多长。A、B 各有 m、n 个起点，每对还要往后扫一趟，三层嵌套，长度一大就跑不完。相邻起点比出的前半截还大量重叠、被反复重算，把「以某两个位置结尾能对齐多长」记下来复用就能省掉。

dp[i][j] 为什么非得钉在以这两个数结尾

定义 dp[i][j] 为：A 的前 i 个数、B 的前 j 个数里，分别以 A[i-1] 和 B[j-1] 结尾的公共连续片段有多长。把结尾钉死这一步不能省——只有规定了以这两个数收尾，连续才有着落；要是定成「任意位置的最长公共片段」，中间断没断就说不清，连续这条约束会漏掉。为了下标不越界，dp 开成 (m+1)×(n+1)，第 0 行第 0 列全填 0，表示有一边没有数时公共长度只能是 0。

相等接左上加一、不等直接归零，凭什么

填 dp[i][j] 只看 A[i-1] 和 B[j-1] 这一对。它俩相等，就把这对接到上一对结尾的片段后面、长度加一，即 dp[i][j] = dp[i-1][j-1] + 1，左上那格记的正是去掉这对之后还连着的那截有多长。它俩不等，以这对结尾就连不起来，直接写 0，从这里重新数起。和最长公共子序列分道，也在这一步：子序列可以跳着挑，不等时取上、左较大的接着攒；子数组必须连续，不等就归零，一点不留。填表时随手用一个变量记下见过的最大 dp 值，就是答案。

拿 [1,2,3,2,1] 和 [3,2,1,4,7] 手填一遍

行对 A、列对 B，第 0 行第 0 列全是 0。第一行 A=1：只有对上 B 的 1 那格 dp[1][3]=dp[0][2]+1=1，其余不等全 0。第二行 A=2：对上 B 的 2，dp[2][2]=dp[1][1]+1=0+1=1。第三行 A=3：对上 B 的 3，dp[3][1]=dp[2][0]+1=1。第四行 A=2：对上 B 的 2，dp[4][2]=dp[3][1]+1=1+1=2，这里接住了上一行的 1。第五行 A=1：对上 B 的 1，dp[5][3]=dp[4][2]+1=2+1=3。全表最大值是 dp[5][3]=3，对应的正是 [3,2,1]，和答案对上。

复杂度落在哪，答案为什么不在右下角

表有 m×n 格，每格只做一次比较和一次加法，时间 O(m·n)；整表要 O(m·n) 空间，但每格只用到左上一格，倒着遍历列就能压成一维，空间降到 O(n)。别拿右下角 dp[m][n] 当答案——最长片段可能收在表里任何位置，得边填边记全局最大。不等时也别顺手写『取上、左较大』，那是子序列的转移，会把断开的片段续上；子数组这里只能归零。

Python

def findLength(A, B):
    m, n = len(A), len(B)
    dp = [[0]*(n+1) for _ in range(m+1)]
    ans = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                ans = max(ans, dp[i][j])
    return ans

C++

int findLength(vector<int>& A, vector<int>& B){
    int m = A.size(), n = B.size(), ans = 0;
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            if(A[i-1] == B[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
                ans = max(ans, dp[i][j]);
            }
    return ans;
}

Java

int findLength(int[] A, int[] B){
    int m = A.length, n = B.length, ans = 0;
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (A[i-1] == B[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                ans = Math.max(ans, dp[i][j]);
            }
    return ans;
}