#718
中等
低频
动态规划最长重复子数组
这是一道围绕数组展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
题目分析
这道题表面上是在处理「最长重复子数组」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 数组 这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：定义
dp[i][j] 为以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度，相等时由左上角状态加 1 转移。推荐代码
推荐解法：动态规划
时间复杂度： O(mn)
空间复杂度： O(mn)
核心思路： 定义
dp[i][j] 为以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度，相等时由左上角状态加 1 转移。class Solution {
public int findLength(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[][] dp = new int[m + 1][n + 1];
int answer = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
answer = Math.max(answer, dp[i][j]);
}
}
}
return answer;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用动态规划，状态表示公共子数组的连续后缀长度。
核心过程
- 定义
dp[i][j]为两个数组在这两个位置结尾时的最长公共子数组长度。 - 如果当前元素相等，就从左上角状态加 1。
- 如果不相等，连续性被打断，当前状态就是 0。
- 遍历过程中维护最大值作为答案。
复杂度总结
时间复杂度 O(mn)，空间复杂度 O(mn)。
面试补一句：要明确区分“公共子数组”和“公共子序列”，状态转移完全不同。
核心思路
这题求的是“连续子数组”，不是子序列，所以状态只能从左上角连续延伸。只要当前位置两个数相等，就能把公共后缀长度再加 1。
步骤讲解
1
定义公共后缀状态
dp[i][j] 表示两个数组分别以 i-1、j-1 结尾时的最长公共子数组长度。
为什么这样做：“以当前位置结尾”正好能表达连续性约束。
对应代码提示：int[][] dp = new int[m + 1][n + 1];
2
相等时从左上角转移
若当前元素相等，则 dp[i][j] = dp[i-1][j-1] + 1；否则为 0。
为什么这样做：连续子数组一旦中断，长度必须清零重新开始。
对应代码提示：if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
3
维护全局最大长度
在遍历中不断更新答案，记录最长公共子数组长度。
为什么这样做：最长值可能出现在任意位置。
对应代码提示：answer = Math.max(answer, dp[i][j]);
易错点
把它写成最长公共子序列
那会允许跳元素，结果不再满足“连续子数组”要求。
正确理解：不相等时必须清零，不能取上方或左方最大值。
状态没有补一行一列空前缀
边界处理会变得很绕，容易越界。
正确理解：使用
m+1 和 n+1 的 DP 表，让空前缀自然作为 0。复杂度与适用判断
时间复杂度：O(mn)
空间复杂度：O(mn)
比其他方案更好在哪里：比暴力枚举所有起点再逐个比较高效得多。
适用判断：题目既有两个序列，又强调“连续”，通常可以考虑公共后缀型 DP。
额外提醒
- 不相等时直接清零，这是和最长公共子序列最大的区别。