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

题目描述：
给定两个整数数组nums1和nums2，以及一个非负整数k。我们需要找到两个数组中最长的公共子数组（连续子数组），但是允许从公共子数组中最多删除k个元素（删除后剩余元素必须保持相对顺序）。换句话说，我们要找到最长的子数组，使得在最多删除k个元素后，两个子数组完全相同。

解题过程：

1. 问题分析：

• 这是最长公共子数组问题的变种，增加了"最多删除k个元素"的灵活性
• 我们需要找到两个数组中连续的子数组，使得它们"几乎相同"
• 删除操作可以理解为允许一定程度的"不对齐"

2. 动态规划状态定义：
   定义dp[i][j][d]表示以nums1的第i个元素和nums2的第j个元素结尾，且已经使用了d次删除操作时，最长公共子数组的长度。

3. 状态转移方程：

• 如果nums1[i] == nums2[j]：
  • 不使用删除：dp[i][j][d] = dp[i-1][j-1][d] + 1
  • 如果d > 0，可以考虑删除当前元素（但这样会中断连续性，所以通常不这样做）
• 如果nums1[i] != nums2[j]：
  • 如果d > 0，我们可以删除这个不匹配的元素：
    dp[i][j][d] = max(dp[i-1][j][d-1], dp[i][j-1][d-1])
  • 如果不删除，当前匹配中断：dp[i][j][d] = 0

4. 更优的二维DP解法：
   实际上我们可以使用二维DP，通过记录当前连续匹配长度和已使用的删除次数：
   定义dp[i][j]为以nums1[i]和nums2[j]结尾时，能达到的最长公共子数组长度（包含删除操作）

但更实用的方法是：对于每个起始位置(i,j)，我们尝试进行匹配，允许最多k次删除：

5. 滑动窗口+双指针解法：
   这是更高效的O(n×m×k)解法：

def findLength(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    max_len = 0
    
    # 尝试所有可能的对齐方式
    for i in range(m):
        for j in range(n):
            # 从当前位置开始匹配
            p1, p2 = i, j
            deletions = 0
            current_len = 0
            
            while p1 < m and p2 < n and deletions <= k:
                if nums1[p1] == nums2[p2]:
                    current_len += 1
                    p1 += 1
                    p2 += 1
                    max_len = max(max_len, current_len)
                else:
                    # 尝试删除nums1中的元素
                    if deletions < k:
                        deletions += 1
                        p1 += 1  # 跳过nums1中的不匹配元素
                    else:
                        break
    
    return max_len

6. 动态规划优化解法：
   使用二维DP，但记录匹配长度和删除次数：

def findLength(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    # dp[i][j][d]表示以i,j结尾，使用d次删除时的最大长度
    dp = [[[0] * (k+1) for _ in range(n+1)] for _ in range(m+1)]
    max_len = 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
                elif d > 0:
                    # 不匹配，但可以使用删除操作
                    # 可以选择删除nums1[i]或nums2[j]
                    dp[i][j][d] = max(dp[i-1][j][d-1], dp[i][j-1][d-1])
                
                max_len = max(max_len, dp[i][j][d])
    
    return max_len

7. 空间优化：
   由于每次只依赖前一行和前一列，可以将空间复杂度优化到O(n×k)：

def findLength(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    # 使用滚动数组优化空间
    prev = [[0] * (k+1) for _ in range(n+1)]
    curr = [[0] * (k+1) for _ in range(n+1)]
    max_len = 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]:
                    curr[j][d] = prev[j-1][d] + 1
                elif d > 0:
                    curr[j][d] = max(prev[j][d-1], curr[j-1][d-1])
                else:
                    curr[j][d] = 0
                
                max_len = max(max_len, curr[j][d])
        prev, curr = curr, prev
    
    return max_len

8. 算法复杂度分析：

• 时间复杂度：O(m×n×k)
• 空间复杂度：O(n×k)（优化后）

这个算法通过动态规划记录了在不同删除次数下的最长匹配长度，既保证了连续性要求，又提供了删除操作的灵活性。