最长重复子数组：算法视频讲解与刷题指南

最长重复子数组：算法视频讲解与刷题指南

我把所有的解题指南整理成：，方便大家在电脑上阅读。这个仓库每天都会更新。请大家去给个star支持一下吧！

同时，我在B站更新了算法视频，同名：代码随机记录

718. 最长重复子数组

问题链接：

给定两个整数数组 A 和 B，返回两个数组中公共子数组和最长子数组的长度。

例子：

进入：

答：[1,2,3,2,1]

B：[3,2,1,4,7]

输出：3

解释：

最长的公共子数组是 [3, 2, 1]。

暗示：

想法

注意，问题中提到的子数组实际上是一个连续的子序列。动态规则最适合解决此类问题。动态规则的五步分析如下：

判断dp数组（dp表）和下标的含义

dp[i][j]：A以下标i - 1结尾，B以下标j - 1结尾。最长重复子数组的长度为dp[i][j]。

这时候细心的同学应该发现了，dp[0][0]是什么意思呢？它不能是以下标-1结尾的A数组。

事实上，dp[i][j]的定义也决定了，当我们遍历dp[i][j]时，i和j都会从1开始。

然后有同学问了，于是我定义dp[i][j]为下标i结尾的A，下标j结尾的B，以及最长重复子数组的长度。不？

没关系！但实施起来比较麻烦一些。看下面的dp数组状态图就可以理解了。

确定递推公式

根据dp[i][j]的定义，dp[i][j]的状态只能从dp[i - 1][j - 1]推导出来。

即当A[i - 1]和B[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + 1；

根据递归公式我们可以看出，遍历i和j都是从1开始的！

如何初始化dp数组

根据dp[i][j]的定义，dp[i][0]和dp[0][j]其实都是没有意义的！

但 dp[i][0] 和 dp[0][j] 需要初始值，因为为了方便递归公式 dp[i][j] = dp[i - 1][j - 1] + 1；

所以dp[i][0]和dp[0][j]被初始化为0。

例如A[0]与B[0]相同，则dp[1][1] = dp[0][0] + 1，只有dp[0][0]初始为0，这是一致的用递归公式一步步相加。

确定遍历顺序

外层for循环遍历A，内层for循环遍历B。

然后另一个同学问，外层for循环遍历B，内层for循环遍历A。不是吗？

好吧，同样的，这里我用外层for循环来遍历A，用内层for循环来遍历B。

同时，这题要求最长子数组的长度。所以遍历的时候，记录dp[i][j]的最大值。

代码如下：

for (int i = 1; i <= A.size(); i++) {
    for (int j = 1; j <= B.size(); j++) {
        if (A[i - 1] == B[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        if (dp[i][j] > result) result = dp[i][j];
    }
}

导出 dp 数组的示例

以例1，A:[1,2,3,2,1],B:[3,2,1,4,7]为例，画出一个dp数组的状态变化，如下：

718. 最长重复子数组

上述五个步骤分析完成后，C++代码如下：

class Solution {
public:
    int findLength(vector& A, vector& B) {
        vector> dp (A.size() + 1, vector(B.size() + 1, 0));
        int result = 0;
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 1; j <= B.size(); j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

滚动数组

下图中：

718. 最长重复子数组

我们可以看到 dp[i][j] 是从 dp[i - 1][j - 1] 导出的。然后压缩成一维数组，即dp[j]由dp[j - 1]推导出来。

相当于将上层dp[i - 1][j]复制到下一层dp[i][j]继续使用。

这时候遍历B数组的时候就需要从后往前遍历，避免重复覆盖。

class Solution {
public:
    int findLength(vector& A, vector& B) {
        vector dp(vector(B.size() + 1, 0));
        int result = 0;
        for (int i = 1; i <= A.size(); i++) {
            for (int j = B.size(); j > 0; j--) {
                if (A[i - 1] == B[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作 
                if (dp[j] > result) result = dp[j];
            }
        }
        return result;
    }
};

原版算法学习手册开放下载！

我把《代码说明》中的二叉树、回溯算法、贪心算法、背包问题等各种主题整理成PDF。它们是绝对必要且透明的！

我们先来预览一些截图：

没什么技巧，直接给出下载地址：

密码：vjqw