带限制的最长重复子数组（限制子数组长度至少为L） 题目描述 ： 给定两个整数数组 nums1 和 nums2 ，以及一个整数 L 。要求找出在两个数组中都出现的最长的、长度 至少为L 的重复子数组的长度。这里的“重复子数组”指的是在两个数组中以相同顺序连续出现的子数组（即公共子数组）。如果不存在长度至少为L的公共子数组，返回0。 示例 ： 输入：nums1 = [ 1,2,3,2,1], nums2 = [ 3,2,1,4,7 ], L = 2 输出：3 解释：最长的公共子数组是 [ 3,2,1 ]，长度为3，且满足长度至少为L=2。 解题过程循序渐进讲解 ： 第一步：理解问题与基础思路 这个问题是“最长重复子数组”的变种，增加了长度至少为L的限制。基础的最长重复子数组问题通常用动态规划解决：定义 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] 的最大值。 但这里我们要求子数组长度至少为L，因此不能简单地取全局最大值，而是需要记录所有长度至少为L的公共子数组的最大长度。 第二步：状态定义调整 沿用基础问题的状态定义： dp[i][j] 表示以 nums1 的第 i-1 个元素和 nums2 的第 j-1 个元素结尾的公共子数组的长度。 初始化： dp[0][j] = 0 ， dp[i][0] = 0 ，表示空数组的情况。 第三步：状态转移与答案更新 转移方程不变： 当 nums1[i-1] == nums2[j-1] 时， dp[i][j] = dp[i-1][j-1] + 1 。 否则 dp[i][j] = 0 。 在计算每个 dp[i][j] 时，如果它的值大于等于L，我们就将其视为一个候选的公共子数组长度。但注意：题目要求的是“长度至少为L的公共子数组”，这意味着我们实际上可以取长度大于等于L的公共子数组，而不仅仅等于L。因此，对于每个 dp[i][j] >= L ，我们可以考虑以当前结尾的、长度至少为L的公共子数组。但这里有一个关键：如果 dp[i][j] >= L ，那么以 (i, j) 结尾的公共子数组的长度是 dp[i][j] ，但我们可以从这个子数组中取出任意长度至少为L的后缀子数组，它们同样也是公共子数组。然而，由于我们关心的是最长的满足条件的公共子数组，我们只需关注 dp[i][j] 本身（因为它是以当前结尾的最长公共子数组的长度）。所以，我们只需要在所有 dp[i][j] >= L 中取最大值即可。 第四步：算法步骤 初始化：设 m = len(nums1) , n = len(nums2) ，创建 (m+1) x (n+1) 的二维数组 dp ，所有元素初始化为0。 初始化答案 ans = 0 。 遍历 i 从1到m，遍历 j 从1到n： 如果 nums1[i-1] == nums2[j-1] ，则 dp[i][j] = dp[i-1][j-1] + 1 。 否则 dp[i][j] = 0 。 如果 dp[i][j] >= L ，则更新 ans = max(ans, dp[i][j]) 。 返回 ans 。 第五步：示例演算 以示例 nums1 = [ 1,2,3,2,1], nums2 = [ 3,2,1,4,7 ], L=2 为例： 构建dp表（只写非零部分）： i=3,j=1: nums1[ 2]=3, nums2[ 0]=3, 相等 -> dp[ 3][ 1 ]=1（小于L，不更新ans）。 i=4,j=2: nums1[ 3]=2, nums2[ 1]=2, 相等 -> dp[ 4][ 2]=dp[ 3][ 1 ]+1=2（>=L，ans=2）。 i=5,j=3: nums1[ 4]=1, nums2[ 2]=1, 相等 -> dp[ 5][ 3]=dp[ 4][ 2 ]+1=3（>=L，ans=3）。 最终ans=3。 第六步：复杂度分析 时间复杂度：O(m n)，因为需要填充整个dp表。 空间复杂度：O(m n)，可以优化为O(min(m, n))，通过滚动数组实现（只保留上一行和当前行）。 第七步：边界情况 如果L大于min(m, n)，则直接返回0，因为不可能有长度至少为L的公共子数组。 如果L <= 0，则问题退化为基础的最长重复子数组问题。 如果数组为空，返回0。 第八步：进一步思考 这个问题也可以使用滑动窗口或二分查找结合哈希的方法来优化时间复杂度，但动态规划解法是最直观且易于理解的。如果L很大，可以先检查L是否超过可能的最大长度，提前返回0。