最长重复子数组（连续）

718. 最长重复子数组

给两个整数数组 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[i] [j] 表示以下标i -1 为结尾的数组1，与以下标j - 1为结尾的数组2的最长公共子数组长度为dp[i] [j]

(注意必须以nums1[i-1]和nums2[j-1]作为公共子序列的结尾元素，因此最终结果要取dp[i] [j]中的最大值)

2.确定递推公式

如果nums1[I-1] = nums2[i-1]，则dp[i] [j] = dp[i-1] [j-1] + 1

表示两个数组的结尾元素相同，新的最长公共子数组长度为不包括这两个结尾元素的最长公共子数组长度+1

dp[i] [j] 需要右移一位表示i-1和j-1为结尾的数组的原因就是为了方便计算

如果nums1[0]和nums2[0]相同，那么dp[1] [1] = dp[0] [0] + 1 = 1

如果使用dp[0] [0] 记录以0为结尾的nums1和以下标0为结尾的nums2，会比较麻烦

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

3.初始化dp数组

根据dp[i] [j]的定义

dp[i] [0] 和 dp[0] [j]都是没有意义的，故初始值置为0，为后续递推做基础

此处可以省略，因为数组初始化为0

for(int j = 0; j < len2+1; j++){
     dp[0][j] = 0;
}
for(int i = 0; i < len1+1; i++){
     dp[i][0] = 0;
}

4.确定遍历顺序

先遍历 i 和 j都可以，因为他们分别表示不同的两个数组

dp数组的状态如图

代码

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[][] dp = new int[len1+1][len2+1];
        //dp[i][j]表示以下标i-1结尾的nums1和以下标j-1结尾的nums2的最长重复子数组
        for(int j = 0; j < len2 + 1; j++){
            dp[0][j] = 0;
        }
        for(int i = 0; i < len1 + 1; i++){
             dp[i][0] = 0;
        }   
        int res = 0;
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                if(dp[i][j] > res) res = dp[i][j];
            }

        }
        return res;
    }
}

• 时间复杂度：$O(n × m)$，n 为nums1长度，m为nums2长度
• 空间复杂度：$O(n × m)$