LC718. 最长重复子数组（HJ75. 公共子串计算）

题目描述

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 示例： 输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。 提示： 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100

题目解析

题目在说什么

这道题给了我们两个数组，比如 A = [1,2,3,2,1] 和 B = [3,2,1,4,7]。我们要找的是：在两个数组中都出现过的、连续的一段数字，并且这段数字要尽可能长。

打个比方：你和你朋友各自写了一张购物清单，你们想看看有没有连续几样东西是两人都买了的，并且想找到最长的那一段连续相同的商品。比如清单A是“苹果、香蕉、橘子、香蕉、苹果”，清单B是“橘子、香蕉、苹果、牛奶、面包”，那么你们共同连续买过的商品就是“橘子、香蕉、苹果”这3样（注意顺序也要一样，并且是连续的）。

这道题就是让我们找出这个最长连续相同片段的长度。示例中答案是3，因为 [3,2,1] 在两个数组中都连续出现了（在A中是第3、4、5个元素，在B中是第1、2、3个元素）。

思路是怎么来的

新手看到这种“找最长公共连续片段”的问题，最容易想到的方法是：把A的每一段都拿出来，去B里找有没有一模一样的连续段。但这样做太慢了，因为A有m个元素，可能的连续段有O(m²)种，每种都要在B里查找，总时间会非常大。

那有没有更聪明的方法呢？我们可以这样想：如果我知道A的前面某一段和B的前面某一段已经匹配了多长，那么当新加一个元素时，我就能很快知道新的匹配长度。比如：

• 假设我们已经知道A的前3个元素[1,2,3]和B的前2个元素[3,2]没有公共的连续子数组（长度为0）。
• 现在比较A的第4个元素（2）和B的第3个元素（1），发现不相等，所以还是0。
• 但当我们比较A的第5个元素（1）和B的第3个元素（1）时，发现相等！这时候，如果A的前4个元素和B的前2个元素已经有了一段公共连续子数组（比如长度是2，即[2,1]和[2,1]），那么加上这个相等的元素，长度就变成了3。

这个思路就是动态规划的核心：用一个小本本记录下“以A的第i个元素结尾”和“以B的第j个元素结尾”的公共连续子数组的长度。这样，当我们处理到新的元素时，只需要看前一对元素的情况，就能快速得到答案。

生活化比喻：想象你在玩拼图，你已经拼好了一部分（前i-1块和前j-1块），现在你拿到两块新拼图（第i块和第j块），如果它们能拼在一起（相等），那么你就能把之前拼好的部分加上这一块，得到更长的连续片段。如果拼不上，那就只能从0开始。

代码逐步拆解

我们来看参考代码，一步一步解释它在做什么。

第一步：获取数组长度

int m = nums1.length;
int n = nums2.length;

这很简单，就是记下两个数组分别有多长。

第二步：创建dp二维数组

int[][] dp = new int[m + 1][n + 1];

这个dp数组就是我们的“小本本”。为什么是m+1和n+1？因为我们要方便地处理“前0个元素”的情况（即数组为空）。dp[i][j]表示：以nums1的第i个元素（注意是第i个，下标是i-1）结尾，并且以nums2的第j个元素（下标j-1）结尾的公共连续子数组的长度。比如dp[3][2]就表示：考虑nums1的前3个元素[1,2,3]和nums2的前2个元素[3,2]，以它们各自的最后一个元素（3和2）结尾的公共连续子数组长度。因为3≠2，所以dp[3][2]=0。

第三步：初始化边界

dp[0][0] = 0;
for( int i = 0 ; i <= m ; i++) dp[i][0] = 0;
for( int j = 0 ; j <= n ; j++) dp[0][j] = 0;

这表示：如果其中一个数组是空的，那肯定没有公共子数组，长度都是0。虽然Java中int数组默认就是0，但这样写更清晰。

第四步：双重循环遍历所有组合

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (nums1[i - 1] == nums2[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            maxLength = Math.max(maxLength, dp[i][j]);
        }
    }
}

这是最核心的部分。i从1到m，j从1到n，相当于我们依次检查每一对元素：nums1的第i个（下标i-1）和nums2的第j个（下标j-1）。