目录
1. 最长重复子数组
1.1 题目解析
1.2 解法
1.3 代码实现
1. 最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 100
1.1 题目解析
题目本质
找 nums1 和 nums2 中 连续片段（子数组） 的最大公共长度。
关键词：连续、公共子数组、最大长度。
本质可以理解为：“在两个序列中，找一段最长的完全一样的连续区间”。
常规解法
枚举 nums1 中的起点 i
枚举 nums2 中的起点 j
从 i, j 开始往后一个个比，下去统计当前公共连续长度
取所有起点组合中的最大值
// 暴力解法：枚举起点 + 向后比对
public int findLengthBruteForce(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;int ans = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int k = 0;while (i + k < n && j + k < m && nums1[i + k] == nums2[j + k]) {k++;}ans = Math.max(ans, k);}}return ans;
}问题分析
最坏情况下：
外层 i 有 n 个位置
中层 j 有 m 个位置
内层 k 最坏比较到 O(min(n, m))
复杂度约为 O(n * m * min(n, m))，当 n, m = 1000 时，量级接近 10^9，会超时。
可以预感
暴力每次“从头比较”，很多重复比较没有复用。
想要更快，就要“记住前面比过的结果”，典型就是 动态规划。
思路转折
观察：如果 nums1[i-1] == nums2[j-1]，那么以这两个位置为结尾的公共子数组长度 = 以前一个位置为结尾的公共子数组长度 + 1。
也就是说，当前结果依赖于“左上方”结果，是标准动态规划形态。
于是我们考虑定义：dp[i][j] = nums1[0..i-1] 和 nums2[0..j-1] 的最长公共后缀长度
则有递推：
若 nums1[i-1] == nums2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
否则：dp[i][j] = 0（因为必须连续）
这样每个状态只做 O(1) 工作，总状态数 O(n*m)，复杂度刚好能压到 10^6 级别，完全可行。
1.2 解法
算法思想
使用二维动态规划
dp[i][j] 表示以 nums1[i-1]、nums2[j-1] 为 结尾 的最长公共子数组长度。
递推公式： dp[i][j] = (nums1[i-1] == nums2[j-1]) ? dp[i-1][j-1] + 1 : 0
扫描过程中维护全局最大值 ans。
i）取 n = nums1.length，m = nums2.length。
ii）申请 int[][] dp = new int[n + 1][m + 1];
多一行一列，用作“哨兵行/列”，避免 i-1、j-1 越界。
iii）外层循环 i 从 1 到 n
iv）内层循环 j 从 1 到 m
若 nums1[i-1] == nums2[j-1]：
dp[i][j] = dp[i-1][j-1] + 1
同时用 dp[i][j] 更新 ans。
否则
dp[i][j] = 0（这里可以省略，因为数组默认 0，但写出来更清晰）。
v）两层循环结束后返回 ans 即为答案。
易错点
下标错位：dp 用的是 1 开始，nums 是 0 开始，内层比较时一定要用 nums1[i-1]、nums2[j-1]。
状态含义搞错：dp[i][j] 是“以 i-1、j-1 为结尾的公共后缀长度”，不是前缀长度，也不是从头开始。
写成最长公共子序列（LCS）思路：LCS 的转移是 max(dp[i-1][j], dp[i][j-1])，会允许不连续，这道题不行，一旦不等就必须断开归零。
1.3 代码实现
class Solution {public int findLength(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;// dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度int[][] dp = new int[n + 1][m + 1];int ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > ans) {ans = dp[i][j]; // 维护全局最大值}} else {dp[i][j] = 0; // 写上更直观（其实默认就是 0）}}}return ans;}
}复杂度分析
时间复杂度： O(n * m)，两重循环，共 n * m 个状态，每个状态 O(1) 转移。
空间复杂度：O(n * m)，使用了一个 (n + 1) * (m + 1) 的二维数组