Shouyu

Appearance

最长重复子数组 ​

题目描述 ​

给两个整数数组 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

题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

文章讲解：https://programmercarl.com/0718.最长重复子数组.html

思路 ​

暴力思路时，这个时间复杂度是 N^3 的。

  • 外层循环遍历nums1的所有起始位置i
  • 中层循环遍历nums2的所有起始位置j
  • 内层循环逐个比较nums1[i...]和nums2[j...]的元素

这个过程中以nums1=[1,2,3], nums2=[3,2,1]为例：

当i=1,j=0时：

  • 会比较[2,3]和[3,2,1]

但这个时候起始位置就已经不同了，对应的子数组自然不是公共的。没有意义。

那怎么优化呢？遇到起始位置不同就不比较吗？

是这个思路，但是可以反着想，起始位置相同我们就接着继续比较，长度不就+1。这样就是利用了之前比较的结果，在比较的结果上继续扩展。

或者直接从结果上观察发现这个规律也是可以的：

这道题我们可以观察示例中公共子数组 [3,2,1] 。假如我们把nums2的后两个元素去掉，结果仍然不变。假如去掉后3个元素，结果就少一个。这说明了什么？

公共子数组长度的增加依赖于是否增加了两个相同的元素。这就是状态的转移，意味着可以基于之前的结果继续扩展

三个关键点。

  • 公共子数组要求连续，所以匹配必须连续
  • dp[i][j]表示以 nums1[i-1] 和 nums2[j-1]结尾的最长公共子数组长度
  • 状态转移：如果当前字符匹配，则长度=前一个匹配结果+1

为什么能用 dp？

  • 最优子结构。最大长度由子问题决定。

  • 根据状态转移，当前状态只依赖前一个状态

动规五部曲 ​

1、dp 数组及下标含义 ​

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。 （特别注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ）.

为什么不定义 dp[i][j] 为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度呢？其实也可以，但后面麻烦，我们先暂且按下不表

2、递推公式 ​

如果 即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;

3、初始化 ​

定义 i 或 j 为0 时的情景。但是定义上是讲不通的，没有以 下标 -1 的元素。所以 我们初始化为0，这样 计算 i 或 j 为1 的时候也能得到正确答案。

4、确定遍历顺序 ​

两个数组地位等价，因此哪个在外层都可以。

题目要求长度最长的子数组的长度。最后一个元素结尾的公共子数组长度不一定最大，因此我们所以在遍历的时候顺便把dp[i][j]的最大值记录下来

5、举例推导 ​

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

718.最长重复子数组

代码实现 ​

C++
int findLength(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    int result = 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;
            }
            if(dp[i][j] > result) result = dp[i][j];
        }
    }
    return result;
}