【leetcode】718. 最长重复子数组

慕雪的小助手正在绞尽脑汁···

慕雪小助手的总结

DeepSeek & LongCat

leetcode刷题笔记-718. 最长重复子数组

题目

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

子数组其实就是连续的子序列。

思路1

说明

依旧是用动态规划的思路，dp数组肯定需要一个二维的了，之前写过最长递增子序列，当时用的dp数组下标的含义是以j下标为结尾的最长递增子序列的长度。本题也是一样的思路

• dp[i][j]代表数组1中以i结尾，数组2中以j结尾的最长公共子数组的长度（包括i和j）；

根据这个定义，可以推算出递推公式，当 nums1[i] == nums2[j] 的时候，说明子数组可以被扩张，此时dp[i][j] = dp[i-1][j-1] +1，含义是当前的最长公共子数组的长度是前一位的最长公共子数组的长度加一（加上当前位）

if(nums1[i] == nums2[j]) {
    dp[i][j] = dp[i-1][j-1] + 1;
}

我们需要对这个dp数组进行初始化，需要初始化第一列和第一行，代码如下

for (int i = 0; i < nums1.size(); i++) {
    // 第一个数组中的元素是否在第二个数组中第一位
    // 在第一位说明最长公共子数组长度是1
    if (nums1[i] == nums2[0]) {
        dp[i][0] = 1;
    }
}
for (int j = 0; j < nums2.size(); j++) {
    // 第一个数组中的元素是否在第二个数组中第一位
    // 在第一位说明最长公共子数组长度是1
    if (nums2[j] == nums1[0]) {
        dp[0][j] = 1;
    }
}

完整代码

随后就是i和j都从1开始遍历了，更新出一个最大值返回就可以了。完整代码如下。

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        // DP 以i和j结尾的元素最长的子数组的长度
        vector<vector<int>> dp(nums1.size(), vector<int>(nums2.size(), 0));
        // 我们要对第一行和第一列进行初始化
        // 判断第二个数组中是否出现了第一个数组中的元素，出现了就算是公共子数组
        bool contains = false;
        for (int i = 0; i < nums1.size(); i++) {
            // 第一个数组中的元素是否在第二个数组中第一位
            // 在第一位说明最长公共子数组长度是1
            if (nums1[i] == nums2[0]) {
                dp[i][0] = 1;
                contains = true;
            }
        }
        for (int j = 0; j < nums2.size(); j++) {
            // 第一个数组中的元素是否在第二个数组中第一位
            // 在第一位说明最长公共子数组长度是1
            if (nums2[j] == nums1[0]) {
                dp[0][j] = 1;
                contains = true;
            }
        }
        int result =
            contains
                ? 1
                : 0; // 如果之前初始化的时候有相同的，那么就设置为1，没有就设置为0
        // 开始遍历，递推思路：如果当前两位相等，那么最长子数组长度就是前一位的子数组长度+1
        // 相当于是以i-1和j-1结尾的最长公共子数组的长度+1
        // dp[i][j] = dp[i-1][j-1]+1
        for (int i = 1; i < nums1.size(); i++) {
            for (int j = 1; j < nums2.size(); j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > result) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }
};

时间复杂度和空间复杂度都是O(N^2)；

思路2

说明

上文的思路中，dp数组下标的含义是以i和j结尾的最长公共子序列的长度。我们可以将其改成dp[i][j]代表以i-1和j-1结尾的最长重复子数组的长度。

这样做就可以不对数组提前进行初始化了，因为dp[0][x] 和dp[x][0]都是没有意义的。

基本思路都是一致的，只不过递推方程的判断改为判断nums1[i-1] == nums2[j-1]了，另外dp数组的长度也需要加一。

完整代码如下

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        // DP 以i和j结尾的元素最长的子数组的长度
        vector<vector<int>> dp(nums1.size() + 1,
                               vector<int>(nums2.size() + 1, 0));
        // 开始遍历，递推思路：如果i,j前两位相等，那么最长子数组长度就是前一位的子数组长度+1
        // 相当于是以i-1和j-1结尾的最长公共子数组的长度+1
        // dp[i][j] = dp[i-1][j-1]+1
        int result = 0;
        for (int i = 1; i < dp.size(); i++) {
            for (int j = 1; j < dp[0].size(); j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > result) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }
};

压缩为一维数组

这道题中的dp递推方程每次都只和[i-1][j-1]有关系，所以可以将二维数组直接压缩为一维，倒叙遍历j就可以沿用上一层dp的结果了，代码如下

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        // DP 以i和j结尾的元素最长的子数组的长度
        vector<int> dp(nums2.size() + 1, 0);
        // 开始遍历，递推思路：如果i,j前两位相等，那么最长子数组长度就是前一位的子数组长度+1
        // 相当于是以i-1和j-1结尾的最长公共子数组的长度+1
        // dp[i][j] = dp[i-1][j-1]+1
        int result = 0;
        // 注意这里是从1遍历到=nums1.size()的位置
        for (int i = 1; i <= nums1.size(); i++) {
            for (int j = nums2.size(); j >= 1; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else {
                    // 不相等需要把这一位设置为初始值（就好比二维矩阵中的初始值）
                    dp[j] = 0;
                }
                if (dp[j] > result) {
                    result = dp[j];
                }
            }
        }
        return result;
    }
};

类似题目

1143. 最长公共子序列

这道题要求是最长的公共子序列，就不是让你算子数组了。虽然题目给出的是字符串，但本质上我们可以把它当作数组来处理，没有区别。

完整的代码如下，采用的是思路2，具体参考注释中的说明。

class Solution {
public:
    int longestCommonSubsequence(string a, string b) {
        int result = 0; // 结果集初始化
        // dp[i][j] 代表a中i和b中j下标和下标之前的最长公共子序列的长度
        // i为0和j为0的情况下，长度为0的字符串是不会有公共子序列的，所以可以全部初始化为0
        vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));
        // 判断 a[i-1] == b[j-1] 代表公共子序列可以扩展
        // dp[i][j] = dp[i-1][j-1] + 1
        // 其他情况，代表公共子序列不能扩展，那么当前的最长公共子序列和前一位的相同
        // 因为是二维数组，所以“前一位”其实有两种情况，分别是i-1和j-1，用max取最大值
        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;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
                if (dp[i][j] > result) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }
};