最长重复子数组问题
字数 1327 2025-12-01 03:00:11
最长重复子数组问题
问题描述
给定两个整数数组 nums1 和 nums2，返回两个数组中公共的、长度最长的子数组的长度。子数组要求连续。例如：
- 输入：
nums1 = [1,2,3,2,1],nums2 = [3,2,1,4,7] - 输出：
3（最长公共子数组为[3,2,1]）
关键点分析
- 子数组 vs 子序列：子数组要求连续，子序列允许不连续（如最长公共子序列 LCS）。
- 暴力法缺陷：枚举所有子数组对比，时间复杂度达 O(n²·m)，效率低。
- 动态规划适用性：需记录以每个位置结尾的公共子数组长度，避免重复计算。
解题步骤（动态规划）
1. 定义状态
设 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度。
- 使用
i-1和j-1是为了避免边界判断，dp[0][j]和dp[i][0]初始为 0。
2. 状态转移方程
- 若
nums1[i-1] == nums2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1。 - 若不等，则
dp[i][j] = 0（因为子数组必须连续）。
3. 初始化与计算
- 初始化
dp为全 0 的二维数组，尺寸为(len(nums1)+1) × (len(nums2)+1)。 - 遍历
i从 1 到len(nums1)，j从 1 到len(nums2)，按转移方程更新dp[i][j]。 - 同时记录全局最大值
max_len = max(max_len, dp[i][j])。
4. 示例推导
以 nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 为例：
| 0 | 3 | 2 | 1 | 4 | 7 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 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 |
最大值 dp[5][3] = 3，对应子数组 [3,2,1]。
5. 复杂度分析
- 时间复杂度：O(n·m)，其中 n、m 为两数组长度。
- 空间复杂度：O(n·m)，可优化至 O(min(n,m))（仅保留上一行或上一列）。
优化技巧
- 滚动数组：因
dp[i][j]只依赖左上方值，可仅用两行数组交替计算。 - 提前终止：若剩余长度不足更新
max_len，可跳过部分循环。
代码实现（Python）
def findLength(nums1, nums2):
m, n = len(nums1), len(nums2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_len = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
return max_len