华为 OD 训练营 · 题解精讲
LC718. 最长重复子数组（HJ75. 公共子串计算）
LC718. 最长重复子数组（HJ75. 公共子串计算） 视频地址：https://uha.xet.tech/s/3nGx3M
题目描述
给两个整数数组 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
题目解析
解题思路
本题要求两个数组中最长公共子数组（连续子序列）的长度。参考代码使用动态规划解决。
定义 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度。当 nums1[i-1] == nums2[j-1] 时，当前元素可以接在前一对元素之后，即 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = 0。最终答案为所有 dp[i][j] 中的最大值。
关键步骤
1. 初始化 dp 数组：大小为 (m+1) × (n+1)，所有元素初始为 0。第 0 行和第 0 列表示其中一个数组为空的情况，公共子数组长度为 0。
2. 双重循环遍历：i 从 1 到 m，j 从 1 到 n，对应比较 nums1[i-1] 和 nums2[j-1]。
3. 状态转移：当元素相等时，dp[i][j] = dp[i-1][j-1] + 1，并更新全局最大值。
示意图（以示例 A=[1,2,3,2,1], B=[3,2,1,4,7] 为例，仅展示部分 dp 值）：
B: 3 2 1 4 7
0 0 0 0 0 0
A: 1 0 0 0 1 0 0
2 0 0 1 0 0 0
3 0 1 0 0 0 0
2 0 0 2 0 0 0
1 0 0 0 3 0 0当 i=5, j=3 时，nums1[4]=1 与 nums2[2]=1 相等，dp[5][3] = dp[4][2] + 1 = 2 + 1 = 3，得到最大值 3。
复杂度分析
- 时间复杂度：O(m × n)，其中 m 和 n 分别为两个数组的长度。需要遍历所有 i、j 组合。
- 空间复杂度：O(m × n)，用于存储 dp 二维数组。
参考代码
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