718. 最长重复子数组

梦里梦外; 2023-10-16 17:46 3阅读 0赞

#### 718. 最长重复子数组 ####

*  题干描述
 *  解题思路
 *   *  1. 确定dp数组（dp table）以及下标的含义
     *  2. 确定递推公式
     *  3. dp数组如何初始化
     *  4. 确定遍历顺序
     *  5. 举例推导dp数组
 *  拓展
 *  代码实现

## 题干描述 ##

[力扣入口][Link 1]

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

示例：

输入：

*  A: \[1,2,3,2,1\]
 *  B: \[3,2,1,4,7\]
 *  输出：3
 *  解释：长度最长的公共子数组是 \[3, 2, 1\] 。

提示：

*  1 <= len(A), len(B) <= 1000
 *  0 <= A\[i\], B\[i\] < 100

## 解题思路 ##

注意题目中说的子数组，其实就是连续子序列。

要求两个数组中最长重复子数组，如果是暴力的解法 只需要先两层for循环确定两个数组起始位置，然后再来一个循环可以是for或者while，来从两个起始位置开始比较，取得重复子数组的长度。

本题其实是动规解决的经典题目，我们只要想到 用二维数组可以记录两个字符串的所有比较情况，这样就比较好推递推公式了。 动规五部曲分析如下：

### 1. 确定dp数组（dp table）以及下标的含义 ###

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

那dp\[0\]\[0\]是什么含义呢？总不能是以下标-1为结尾的A数组吧。

其实dp\[i\]\[j\]的定义也就决定着，我们在遍历dp\[i\]\[j\]的时候i 和 j都要从1开始。

那如果定义dp\[i\]\[j\]为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度。不行么？

行倒是行！ 但实现起来就麻烦一点，需要单独处理初始化部分。

### 2. 确定递推公式 ###

根据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开始！

### 3. 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，正好符合递推公式逐步累加起来。

### 4. 确定遍历顺序 ###

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

那外层for循环遍历B，内层for循环遍历A，可以么？

也行，一样的，我这里就用外层for循环遍历A，内层for循环遍历B了。

同时题目要求长度最长的子数组的长度。所以在遍历的时候顺便把dp\[i\]\[j\]的最大值记录下来。

代码如下：

for(int i = 1; i <= nums1.size(); i++){
        
    	for(int j = 1; j <= nums2.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];
    	}
    }

### 5. 举例推导dp数组 ###

拿示例1中，A: \[1,2,3,2,1\]，B: \[3,2,1,4,7\]为例，画一个dp数组的状态变化，如下：  
![在这里插入图片描述][ff6bb8a0d74c4afa937b5b636ad5c8d6.png]

## 拓展 ##

前面讲了 dp数组为什么定义：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp\[i\]\[j\]。

我就定义dp\[i\]\[j\]为 以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度。不行么？

当然可以，就是实现起来麻烦一些。

如果定义 dp\[i\]\[j\]为 以下标i为结尾的A，和以下标j 为结尾的B，那么 第一行和第一列毕竟要进行初始化，如果nums1\[i\] 与 nums2\[0\] 相同的话，对应的 dp\[i\]\[0\]就要初始为1， 因为此时最长重复子数组为1。 nums2\[j\] 与 nums1\[0\]相同的话，同理。

## 代码实现 ##

class Solution {
        
        // 718.最长重复子数组
        public int findLength(int[] nums1, int[] nums2){
        
            int result = 0;
            int[][] dp = new int[nums1.length + 1][nums2.length + 1];
    
            for(int i = 1; i < nums1.length + 1; i++){
        
                for(int j = 1; j < nums2.length + 1; j++){
        
                    if(nums1[i - 1] == nums2[j - 1]){
        
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        result = Math.max(result, dp[i][j]);
                    }
                }
            }
            return result;
        }
    }

**参考资料**：[代码随想录-718. 最长重复子数组][-718.]

[Link 1]: https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
[ff6bb8a0d74c4afa937b5b636ad5c8d6.png]: https://img-blog.csdnimg.cn/ff6bb8a0d74c4afa937b5b636ad5c8d6.png
[-718.]: https://programmercarl.com/0718.%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE