力扣718-最长重复子数组（Java详细题解）

题目链接：718. 最长重复子数组 - 力扣（LeetCode）

前情提要：

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组利于debug。

每一个dp题目如果都用这五步分析清楚，那么这道题就能解出来了。

题目思路:

如果没有接触过子序列问题，那么第一次做这个题还是很有难度。

本题要求俩个数组中的公共最长连续子序列。

注意这里是要求连续的。

那么如果你做过674. 最长连续递增序列 - 力扣（LeetCode）或者看了我的题解力扣674-最长连续递增序列（Java详细题解）-CSDN博客，那么会好理解这道题一点。

话不多说，直接开始我们的dp五部曲。

1.确定dp数组和i下标的含义。

该题是要求俩个数组公共的子数组长度，那我们就要比较俩个数组的任意俩个元素。那我们是不是要用二维的dp数组来记录下这个状态呀。

用二维dp数组来记录每一个数组元素和另一个数组元素相比较的结果。

所以就要用到dp[i] [j]了。

注意这里dp[i] [j]的含义是指以i - 1结尾的数组和j - 1为结尾的数组俩个数组的最长公共子序列。

这里的dp含义在下面很多篇都会用到，大家要牢记这点。

至于为什么要设置i - 1和j - 1这样的含义，我们在初始化那个环节会讲，这里大家记住这个定义就好。

2.确定递推公式。

因为是要求公共的子数组，所以可能是当nums[i - 1] == nums[j - 1]的时候加入我们的结果。

为什么是i - 1和j - 1？

因为dp数组定义的就是i - 1结尾的数组和j - 1为结尾的数组俩个数组的最长公共子序列，所以只有nums[i - 1] == nums[j - 1]时，他们的dp[i] [j]才能被推出。

dp[i] [j] = 什么呢？

当nums[i - 1] == nums[j - 1]的时候，dp[i] [j] = dp[i - 1] [j - 1] + 1。

因为是求连续的公共数组，所以dp[i] [j] 只与他们前面一个状态dp[i - 1] [j - 1]有关。

当nums[i - 1] == nums[j - 1]，dp[i] [j]是由dp[i - 1] [j - 1]（下标i - 2结尾的数组和j - 2为结尾的数组俩个数组的最长公共子序列长度）加上 nums[i - 1] nums[j - 1]这俩个元素相同的长度，也就是1。

所以dp[i] [j] = dp[i - 1] [j - 1] + 1。

3.dp初始化。

该题的初始化部分很重要。

由递推公式可以看出，每一个dp[i] [j]在二维数组中都是由它左上的位置得出，所以要初始化dp[i] [0]和dp[0] [i]。也就是第一排和第一列。

由于dp数组定义的是以i - 1结尾的数组和j - 1为结尾的数组俩个数组的最长公共子序列。

所以第一排(dp[0] [i]）是以下标-1为结尾的数组和i - 1为结尾的数组俩个数组的最长公共子序列。

以下标-1为结尾的数组不存在，所以他们的最长公共子序列自然就为0。

第一列同理可以得出也都初始化为0。

这就是我们为什么将dp数组定义为以i - 1和j - 1为结尾的数组的最长公共子序列。

这样便于初始化。如果定义为以i和j为结尾的数组最长公共子序列。

那么第一排第一列初始化就不一样了。

他们第一排和第一列是有意义的，并且他们还可能相同。

所以要遍历一遍第一列和第一排，如果nums[i] == nums[j] 那么dp[i] [j] = 1。

因为他们的值相同，第一排和第一列的最长公共子序列就为该元素。

4.确定dp的遍历顺序。

由递推公式可以看出dp[i] [j] 由dp[i - 1] [j - 1]可得。所以要从左到右，从上到下去遍历。

5.如果没有ac打印dp数组利于debug。

在这里插入图片描述

最终代码：

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        //这里的dp含义是 以i - 1和j - 1为结尾的俩个数组最长子数组的长度。
        //为什么 定义 i- 1和 j - 1呢 是为了初始化方便。
        //递推公式 当nums1[i - 1] == nums2[j - 1] 说明俩个数组出现相等的值了 既然出现相等的值了
        //那我的dp[i][j] 就要加1了 因为我dp[i][j]是记录的i - 1和j - 1为结尾的俩个数组最长子数组的长度
        //那么在哪个状态上家呢？
        //其实子数组就是一种连续子序列 他的状态只与他的前一状态有关  所以与dp[i - 1][j - 1]有关
        //那么dp[i][j] = dp[i - 1][j - 1] + 1
        //紧接着我们就要进行初始化了
        //
        int [][] dp = new int [nums1.length + 1][nums2.length + 1];
        int result = 0;
        for(int i = 1;i <= nums1.length;i ++){
            for(int j = 1;j <= nums2.length;j ++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                //因为只有nums1[i - 1] == nums2[j - 1]才会进入我们的dp数组，所以任意位置的dp数组都可能是最大的，所以我们要遍历一遍求最大的。
                result = Math.max(result,dp[i][j]);
            }
        }
        return result;
    }
}