线性动态规划：最长重复子数组的变种——限制子数组长度至少为L且最多允许k次不匹配

题目描述

给定两个整数数组 nums1 和 nums2（长度分别为 n 和 m），以及两个整数 L 和 k，求两个数组中相同长度子数组的最大长度，要求：

1. 子数组长度至少为 L。
2. 在子数组中，对应位置元素不同的个数不超过 k 次（即允许最多 k 次不匹配）。

例如：
nums1 = [1, 2, 3, 4, 5]
nums2 = [2, 2, 3, 5, 5]
L = 2, k = 1
满足条件的最长子数组可以是 [2, 3]（在 nums1 中索引 1~2，nums2 中索引 0~1，不匹配次数为 0）或 [3, 4, 5] 与 [3, 5, 5]（不匹配次数为 1，长度 3，但需注意对齐方式）。

解题思路分析

这是一个带约束的最长公共子数组问题。

• 经典最长公共子数组（无 k 和 L 限制）可以用动态规划 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组长度。
• 现在加入两个约束：
  1. 长度至少为 L
  2. 最多允许 k 次不匹配

如果我们直接扩展 dp 状态，可以定义：
dp[i][j][t] = 以 nums1[i-1] 和 nums2[j-1] 结尾的子数组长度，并且该子数组中不匹配元素个数为 t。
然后检查当 t ≤ k 且长度 dp[i][j][t] ≥ L 时更新答案。

具体步骤详解

步骤 1：定义状态

dp[i][j][t] 表示：

• 考虑 nums1 的前 i 个元素和 nums2 的前 j 个元素
• 以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组长度
• 并且在该子数组中，对应位置元素不同的个数为 t（不匹配次数）

注意：t 的范围是 0 到 k，因为超过 k 的不匹配就无效了。

步骤 2：状态转移

情况 1：nums1[i-1] == nums2[j-1]

• 如果相等，那么可以从 dp[i-1][j-1][t] 转移过来，并且不匹配次数 t 不变。
• 转移方程：
  dp[i][j][t] = dp[i-1][j-1][t] + 1（前提是 i>0, j>0）

情况 2：nums1[i-1] != nums2[j-1]

• 如果不相等，那么不匹配次数需要增加 1。
• 转移方程：
  dp[i][j][t] = dp[i-1][j-1][t-1] + 1（前提是 i>0, j>0, t>0）

初始化：
dp[0][j][t] = 0, dp[i][0][t] = 0，表示空数组。

步骤 3：处理长度至少为 L

在更新 dp[i][j][t] 后，如果 dp[i][j][t] ≥ L 且 t ≤ k，那么可以更新答案：
ans = max(ans, dp[i][j][t])
因为题目要求子数组长度至少 L，所以只要长度满足，就可能是候选解。

步骤 4：空间优化

dp[i][j][t] 空间复杂度 O(n*m*k)，可能较大。
注意到 dp[i][j] 只依赖于 dp[i-1][j-1]，所以可以用滚动数组优化到 O(m*k)，但需注意遍历顺序（从后往前更新 t）。

示例演算

以 nums1 = [1, 2, 3, 4, 5], nums2 = [2, 2, 3, 5, 5], L=2, k=1 为例：

我们只关注部分关键位置：

1. 初始化所有 dp[i][j][t]=0。
2. 遍历 i=1..n, j=1..m：
   • i=1, j=1: nums1[0]=1, nums2[0]=2，不相等，t=1 时 dp[1][1][1]=1（长度1，不匹配1次），但长度 <L，不更新答案。
   • i=2, j=1: nums1[1]=2, nums2[0]=2，相等，t=0 时 dp[2][1][0]=dp[1][0][0]+1=1，长度<L。
   • i=2, j=2: nums1[1]=2, nums2[1]=2，相等，t=0 时 dp[2][2][0]=dp[1][1][0]+1=1（因为之前 dp[1][1][0]=0），长度=1<L。
   • 逐步推进...
   • i=3, j=3: nums1[2]=3, nums2[2]=3，相等，dp[3][3][0]=dp[2][2][0]+1=2（因为之前 dp[2][2][0]=1）。
     此时长度=2 ≥L，不匹配次数=0 ≤k，更新 ans=2。
   • 继续计算到 i=5, j=5：
     nums1[4]=5, nums2[4]=5，相等，继承之前状态。
     检查 i=5, j=4：nums1[4]=5, nums2[3]=5 相等，若之前 dp[4][3][t] 状态中有长度 3，这里会延伸到长度 4，需追溯匹配链。

实际上，最长可能子数组：
在 nums1[2..4] = [3,4,5] 与 nums2[2..4] = [3,5,5] 中：

• 对应比较：(3,3) 匹配，(4,5) 不匹配（t=1），(5,5) 匹配。
  长度=3，不匹配次数=1 ≤k，且长度 ≥L=2，所以 ans 可以更新为 3。

代码框架（Python 思路）

def longestCommonSubarrayWithConstraints(nums1, nums2, L, k):
    n, m = len(nums1), len(nums2)
    dp = [[[0]*(k+1) for _ in range(m+1)] for _ in range(n+1)]
    ans = 0
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            for t in range(0, k+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j][t] = dp[i-1][j-1][t] + 1
                else:
                    if t > 0:
                        dp[i][j][t] = dp[i-1][j-1][t-1] + 1
                    else:
                        dp[i][j][t] = 0  # 不匹配且 t=0 时不能延续
                
                if dp[i][j][t] >= L:
                    ans = max(ans, dp[i][j][t])
    
    return ans

总结

这个变种问题通过三维动态规划，在经典最长公共子数组基础上增加了不匹配次数的维度，并在更新过程中检查长度约束。

• 时间复杂度：O(nmk)
• 空间复杂度可优化到 O(m*k)
  该思路能系统化处理允许不匹配的公共子数组问题，并灵活加入长度下限约束，适合多种类似变种题目。