nums1 = [1,2,3,2,1]  
nums2 = [3,2,1,4,7]  
最长重复子数组为 [3,2,1]，长度为 3。

nums1: [1,2,3,2,1]  
nums2: [3,2,1,4,7]  

最长重复子数组问题 题目描述 给定两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度。子数组要求连续。例如： 解题思路 本题要求的是 连续子数组 的匹配，与不要求连续的子序列问题不同。我们将通过动态规划（DP）和滑动窗口两种方法详细讲解。 方法一：动态规划（DP） 步骤分析 定义状态 ： 设 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度。 （使用 i-1 和 j-1 是为了避免边界判断， dp[0][j] 或 dp[i][0] 表示空数组匹配，初始为0。） 状态转移方程 ： 若 nums1[i-1] == nums2[j-1] ，则 dp[i][j] = dp[i-1][j-1] + 1 。 否则 dp[i][j] = 0 （因为子数组必须连续，一旦不匹配，长度重置为0）。 初始化 ： dp[0][j] = 0 ， dp[i][0] = 0 。 计算过程 ： 遍历 i 从 1 到 len(nums1) ， j 从 1 到 len(nums2) ，更新 dp[i][j] 并记录最大值。 举例演算 （用题目例子）： DP 表（行列多一行一列用于初始化）： | | 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] 。 复杂度分析 ： 时间复杂度：O(mn) 空间复杂度：O(mn)（可优化为 O(min(m,n))） 方法二：滑动窗口 核心思想 将两个数组对齐，通过相对滑动找到重叠部分的最大匹配。例如： 将 nums2 的头部对齐 nums1 的每个位置（或反之），计算重叠部分的最长公共前缀。 步骤详解 枚举对齐方式 ： 固定 nums1，移动 nums2 使其头部与 nums1 的某个位置对齐。 对齐方式共有 m + n - 1 种（m 和 n 为数组长度）。 计算重叠区间 ： 对于每种对齐，计算重叠部分的长度 len ，然后在重叠区间内遍历比较 nums1[i] 和 nums2[j] 。 维护当前匹配长度 ： 若元素相等，当前匹配长度加1，更新最大值。 若不等，重置当前匹配长度为0。 举例对齐过程 （部分关键对齐）： 对齐方式1：nums2 的头部对齐 nums1 的索引2（元素3） 重叠部分： nums1[2:5] = [3,2,1] ， nums2[0:3] = [3,2,1] 比较得到连续匹配长度3。 其他对齐方式可能匹配长度更短。 复杂度分析 ： 时间复杂度：O((m+n) * min(m,n)) 空间复杂度：O(1) 总结 动态规划 是通用解法，思路直接，适合所有输入规模。 滑动窗口 在数组长度差异大时可能更优，但最坏情况不如DP。 面试中建议先实现DP，再讨论滑动窗口的优化思路。