带限制的最长重复子数组（限制子数组长度至少为L）

题目描述

给定两个整数数组 nums1 和 nums2，以及一个整数 L。
要求找出在两个数组中长度至少为 L 的公共连续子数组（即重复子数组）的最大长度。

例如：

• nums1 = [1, 2, 3, 2, 1, 4, 5]
• nums2 = [3, 2, 1, 4, 1, 2, 3]
• L = 3
  可能的最长重复子数组是 [3, 2, 1] 或 [1, 4] 等，但长度至少为 3 的最长重复子数组是 [3, 2, 1]，长度为 3。
  如果 L=4，则不存在长度 ≥4 的公共连续子数组，答案为 0。

解题思路

1. 基本问题回顾

如果没有“长度至少为 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，否则为 0。
• 答案就是所有 dp[i][j] 的最大值。

2. 加入长度限制 L

现在要求长度至少为 L 的公共子数组。

• 如果某个 dp[i][j] = k，那么以 (i-k+1, j-k+1) 到 (i, j) 这两个位置结尾的子数组长度是 k。
• 只有当 k >= L 时，它才符合条件。

但是，我们最终要的是整个符合条件的公共子数组的最大长度，而不仅仅是以某个位置结尾的长度。
换句话说，如果存在一个公共子数组长度为 5，那么它一定在某个 dp[i][j] = 5 中被记录，并且 5 ≥ L，所以可以直接用 5 更新答案。

但注意：
如果 dp[i][j] = 7，那么它的所有后缀（长度 ≥ L 的部分）也都满足条件，但我们只关心整个 7 的长度。
所以，实际上我们只需要在计算 dp[i][j] 时，如果它的值 ≥ L，就用它更新答案。

3. 为什么不能直接取 max(dp[i][j])？

因为 dp[i][j] 记录的是以 i, j 结尾的匹配长度，如果整个公共子数组很长，它会在最后一个匹配位置被记录。
例如：
nums1: [1,2,3,4,5]
nums2: [1,2,3,4,5]
L=3
dp[5][5] = 5，它代表了整个长度 5 的公共子数组。
所以答案就是 5。

结论：

• 先按普通最长公共子串计算 dp 表。
• 在计算过程中，如果 dp[i][j] >= L，就用 dp[i][j] 更新最终答案。

动态规划步骤详解

状态定义

dp[i][j]：以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度。

• 这里用 i-1, j-1 是为了避免边界判断，让 i, j 从 1 到 n/m。
• 空间可优化为一维数组。

状态转移方程

1. 如果 nums1[i-1] == nums2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
2. 否则 dp[i][j] = 0。

在更新过程中，如果 dp[i][j] >= L，就更新 ans = max(ans, dp[i][j])。

初始化

dp[0][j] = 0, dp[i][0] = 0。

例子演示

nums1 = [1, 2, 3, 2, 1, 4, 5]
nums2 = [3, 2, 1, 4, 1, 2, 3]
L = 3

普通 dp 表（只写匹配部分）：

• 当 i=3 (nums1[2]=3), j=1 (nums2[0]=3) → dp[3][1]=1（长度=1<L，不更新答案）
• 当 i=4 (nums1[3]=2), j=2 (nums2[1]=2) → dp[4][2]=1
• 当 i=5 (nums1[4]=1), j=3 (nums2[2]=1) → dp[5][3]=1
  这里注意，dp[4][2]=1 不连续，所以这里新匹配，dp=1。

再看 i=4 (nums1[3]=2), j=5 (nums2[4]=2) 的匹配：

• 看前一位 i=3 (nums1[2]=3), j=4 (nums2[3]=4) 不匹配，所以 dp[4][5]=1

其实最长匹配是 i=3,4,5 对应 j=1,2,3：
nums1[2]=3, nums2[0]=3 → dp[3][1]=1
nums1[3]=2, nums2[1]=2 → dp[4][2] = dp[3][1]+1=2
nums1[4]=1, nums2[2]=1 → dp[5][3] = dp[4][2]+1=3（此时长度=3≥L，更新 ans=3）

继续看 i=6 (nums1[5]=4), j=4 (nums2[3]=4) → dp=1
i=7 (nums1[6]=5) 无匹配。

最终 ans=3。

优化空间

由于 dp[i][j] 只依赖 dp[i-1][j-1]，可以用一维数组，内层从后往前遍历 nums2 以避免覆盖。

• 用 dp[j] 表示当前行以 nums2[j-1] 结尾的长度。
• 用 prev 保存 dp[i-1][j-1]。

伪代码

function longestCommonSubarrayAtLeastL(nums1, nums2, L):
    n, m = len(nums1), len(nums2)
    dp = [0] * (m+1)
    ans = 0
    for i in 1..n:
        prev = 0
        for j in 1..m:
            temp = dp[j]  # 保存上一行的 dp[j]，即 dp[i-1][j]
            if nums1[i-1] == nums2[j-1]:
                dp[j] = prev + 1
                if dp[j] >= L:
                    ans = max(ans, dp[j])
            else:
                dp[j] = 0
            prev = temp
    return ans

复杂度

• 时间复杂度：O(n*m)
• 空间复杂度：O(m)

思考扩展

1. 如果要求返回具体的子数组内容，可以在更新 ans 时记录位置。
2. 如果 L 很大，可以在 dp 计算时只考虑长度 ≥ L 的匹配，但这不影响最坏复杂度。
3. 此题也可以用后缀自动机或哈希+二分，但动态规划最直观。