# LeetCode 718、最长重复子数组（HJ75. 公共子串计算）
# 一、题目描述
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
提示：
1 <= len(A), len(B) <= 10000 <= A[i], B[i] < 100
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最长重复子数组（ LeetCode 718 ）：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray
class Solution {
public int findLength(int[] nums1, int[] nums2) {
// 获取 nums1 的长度
int m = nums1.length;
// 获取 nums2 的长度
int n = nums2.length;
// 设置数组 dp，用来存储 nums1 和 nums2 公共的、长度最长的子数组的长度
// dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
// dp[2][3] 表示 nums1 前 2 个元素和 nums2 前 3 个元素的公共的、长度最长的子数组的长度
// dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
// 前 i 个元素的区间为 [ 0 ， i - 1 ]
// dp[m][n] 表示 nums1 前 m 个元素和 nums2 前 n 个元素的公共的、长度最长的子数组的长度
// 前 m 个元素的表示区间为 [ 0 ,m ]，前 n 个元素的表示区间为 [ 0 ,n ]
// 因此，dp 数组的长度为 m + 1 和 n + 1
int[][] dp = new int[m + 1][n + 1];
// maxLength 表示 dp 数组中的最大值
int maxLength = 0;
// dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
// nums1 nums2 也没有元素
// 因此，公共的、长度最长的子数组的长度为 0
dp[0][0] = 0;
// nums1 没有元素 或者 nums2 没有字符时，公共的、长度最长的子数组的长度都为 0
for( int i = 0 ; i <= m ; i++){
dp[i][0] = 0;
}
for( int j = 0 ; j <= n ; j++){
dp[0][j] = 0;
}
// i 从 1 开始，直到 m 位置，遍历 nums1 的前 i 个元素
for (int i = 1; i <= m; i++) {
// j 从 1 开始，直到 n 位置，遍历 nums2 的前 j 个元素
for (int j = 1; j <= n; j++) {
// 如果发现 nums1 的当前元素，即位置为 i - 1 的元素
// 与 nums2 的当前元素，即位置为 j - 1 的元素【相同】
// 此时，找到了一个公共元素，公共的、长度最长的子数组的长度加 1
if (nums1[i - 1] == nums2[j - 1]) {
// dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
// dp[i - 1][j - 1] 表示 nums1 前 i - 1 个元素和 nums2 前 j - 1 个元素的公共的、长度最长的子数组的长度
dp[i][j] = dp[i - 1][j - 1] + 1;
// 更新最长的子数组长度
maxLength = Math.max(maxLength, dp[i][j]);
}
}
}
// 返回结果
return maxLength;
}
}
# **2、**C++ 代码
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
// 获取 nums1 的长度
int m = nums1.size();
// 获取 nums2 的长度
int n = nums2.size();
// 设置数组 dp，用来存储 nums1 和 nums2 公共的、长度最长的子数组的长度
// dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
// dp[2][3] 表示 nums1 前 2 个元素和 nums2 前 3 个元素的公共的、长度最长的子数组的长度
// dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
// 前 i 个元素的区间为 [ 0 ， i - 1 ]
// dp[m][n] 表示 nums1 前 m 个元素和 nums2 前 n 个元素的公共的、长度最长的子数组的长度
// 前 m 个元素的表示区间为 [ 0 ,m ]，前 n 个元素的表示区间为 [ 0 ,n ]
// 因此，dp 数组的长度为 m + 1 和 n + 1
auto dp = vector < vector < int>> ( m + 1 ,vector<int> ( n + 1 ));
// maxLength 表示 dp 数组中的最大值
int maxLength = 0;
// dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
// nums1 nums2 也没有元素
// 因此，公共的、长度最长的子数组的长度为 0
dp[0][0] = 0;
// nums1 没有元素 或者 nums2 没有字符时，公共的、长度最长的子数组的长度都为 0
for( int i = 0 ; i <= m ; i++){
dp[i][0] = 0;
}
for( int j = 0 ; j <= n ; j++){
dp[0][j] = 0;
}
// i 从 1 开始，直到 m 位置，遍历 nums1 的前 i 个元素
for (int i = 1; i <= m; i++) {
// j 从 1 开始，直到 n 位置，遍历 nums2 的前 j 个元素
for (int j = 1; j <= n; j++) {
// 如果发现 nums1 的当前元素，即位置为 i - 1 的元素
// 与 nums2 的当前元素，即位置为 j - 1 的元素【相同】
// 此时，找到了一个公共元素，公共的、长度最长的子数组的长度加 1
if (nums1[i - 1] == nums2[j - 1]) {
// dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
// dp[i - 1][j - 1] 表示 nums1 前 i - 1 个元素和 nums2 前 j - 1 个元素的公共的、长度最长的子数组的长度
dp[i][j] = dp[i - 1][j - 1] + 1;
// 更新最长的子数组长度
maxLength = max(maxLength, dp[i][j]);
}
}
}
// 返回结果
return maxLength;
}
};
# 3、Python 代码
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
# 获取 nums1 的长度
m = len(nums1)
# 获取 nums2 的长度
n = len(nums2)
# 设置数组 dp，用来存储 nums1 和 nums2 公共的、长度最长的子数组的长度
# dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
# dp[2][3] 表示 nums1 前 2 个元素和 nums2 前 3 个元素的公共的、长度最长的子数组的长度
# dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
# 前 i 个元素的区间为 [ 0 ， i - 1 ]
# dp[m][n] 表示 nums1 前 m 个元素和 nums2 前 n 个元素的公共的、长度最长的子数组的长度
# 前 m 个元素的表示区间为 [ 0 ,m ]，前 n 个元素的表示区间为 [ 0 ,n ]
# 因此，dp 数组的长度为 m + 1 和 n + 1
dp = [[0] * (n + 1 ) for _ in range( m + 1 )]
# maxLength 表示 dp 数组中的最大值
maxLength = 0
# dp[0][0] 表示 nums1 前 0 个元素和 nums2 前 0 个元素的公共的、长度最长的子数组的长度
# nums1 nums2 也没有元素
# 因此，公共的、长度最长的子数组的长度为 0
dp[0][0] = 0
# nums1 没有元素 或者 nums2 没有字符时，公共的、长度最长的子数组的长度都为 0
for i in range( 0 , m + 1 ) :
dp[i][0] = 0
for j in range( 0 , n + 1 ) :
dp[0][j] = 0
# i 从 1 开始，直到 m 位置，遍历 nums1 的前 i 个元素
for i in range( 1 , m + 1 ) :
# j 从 1 开始，直到 n 位置，遍历 nums2 的前 j 个元素
for j in range( 1 , n + 1 ) :
# 如果发现 nums1 的当前元素，即位置为 i - 1 的元素
# 与 nums2 的当前元素，即位置为 j - 1 的元素【相同】
# 此时，找到了一个公共元素，公共的、长度最长的子数组的长度加 1
if nums1[i - 1] == nums2[j - 1] :
# dp[i][j] 表示 nums1 前 i 个元素和 nums2 前 j 个元素的公共的、长度最长的子数组的长度
# dp[i - 1][j - 1] 表示 nums1 前 i - 1 个元素和 nums2 前 j - 1 个元素的公共的、长度最长的子数组的长度
dp[i][j] = dp[i - 1][j - 1] + 1
# 更新最长的子数组长度
maxLength = max(maxLength, dp[i][j])
# 返回结果
return maxLength