最长重复子数组的变种：最多允许删除k个元素的最长公共子数组

我将为您详细讲解这个线性动态规划问题。这个问题是经典最长重复子数组问题的扩展版本，增加了删除操作的约束条件。

问题描述

给定两个整数数组 nums1 和 nums2，以及一个整数 k。我们需要找到最长的公共子数组，其中允许从任意一个数组中最多删除 k 个元素。换句话说，我们可以在 nums1 或 nums2 中跳过最多 k 个元素，来匹配另一个数组中的连续元素序列。

示例：

nums1 = [1, 2, 3, 4, 5]
nums2 = [2, 3, 1, 4, 5]
k = 1
输出：4
解释：可以删除 nums2 中的元素1，得到公共子数组 [2, 3, 4, 5]，长度为4

解题思路

步骤1：理解问题本质

这个问题与标准的最长公共子数组问题不同之处在于：

• 标准问题要求完全连续的匹配
• 本问题允许在匹配过程中跳过最多k个元素
• 这相当于在匹配时有一定的"容错"能力

步骤2：定义状态

我们使用三维动态规划：

• dp[i][j][d] 表示以 nums1[i-1] 和 nums2[j-1] 结尾，且已经使用了 d 次删除操作的最长公共子数组长度

其中：

• i 表示在 nums1 中考虑前i个元素
• j 表示在 nums2 中考虑前j个元素
• d 表示已经使用的删除次数（0 ≤ d ≤ k）

步骤3：状态转移方程

对于每个位置 (i, j) 和删除次数 d：

1. 如果当前元素匹配（nums1[i-1] == nums2[j-1]）：

   • 我们可以直接扩展前面的匹配：dp[i][j][d] = dp[i-1][j-1][d] + 1

2. 如果当前元素不匹配：

   • 我们可以选择从 nums1 中删除当前元素（如果还有删除次数）：
     dp[i][j][d] = dp[i-1][j][d-1] （如果 d > 0）
   • 或者从 nums2 中删除当前元素（如果还有删除次数）：
     dp[i][j][d] = dp[i][j-1][d-1] （如果 d > 0）
   • 或者重新开始计数：dp[i][j][d] = 0

步骤4：初始化

• 当 i = 0 或 j = 0 时，dp[i][j][d] = 0（空数组没有公共子数组）
• 删除次数d必须满足 0 ≤ d ≤ k

步骤5：算法实现

def longestCommonSubarrayWithDeletions(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    
    # 创建三维DP数组
    dp = [[[0] * (k + 1) for _ in range(n + 1)] for _ in range(m + 1)]
    max_length = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            for d in range(k + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    # 元素匹配，直接扩展
                    dp[i][j][d] = dp[i - 1][j - 1][d] + 1
                else:
                    # 元素不匹配
                    if d > 0:
                        # 可以选择从nums1或nums2中删除一个元素
                        option1 = dp[i - 1][j][d - 1] if d > 0 else 0
                        option2 = dp[i][j - 1][d - 1] if d > 0 else 0
                        dp[i][j][d] = max(option1, option2)
                    else:
                        # 没有删除次数可用，重新开始
                        dp[i][j][d] = 0
                
                # 更新最大长度
                max_length = max(max_length, dp[i][j][d])
    
    return max_length

步骤6：复杂度分析

• 时间复杂度：O(m × n × k)，其中m和n分别是两个数组的长度
• 空间复杂度：O(m × n × k)，可以通过滚动数组优化到O(n × k)

步骤7：示例演示

让我们用之前的例子来验证：

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

计算过程：

• 当匹配到 nums1[1]=2 和 nums2[0]=2 时，开始匹配
• 继续匹配 nums1[2]=3 和 nums2[1]=3
• 遇到 nums1[3]=4 和 nums2[2]=1 不匹配，使用一次删除跳过nums2中的1
• 继续匹配 nums1[3]=4 和 nums2[3]=4，nums1[4]=5 和 nums2[4]=5
• 最终得到长度为4的公共子数组

优化思路

1. 空间优化：使用滚动数组将空间复杂度降为O(n × k)
2. 提前终止：当剩余长度不足以更新最大值时提前终止
3. 记忆化搜索：可以使用自顶向下的记忆化搜索实现

这个算法很好地平衡了匹配的连续性和删除操作的灵活性，是处理带容错的最长公共子数组问题的有效解决方案。