最长重复子数组的变种：最多允许k次元素替换的最长公共子数组

题目描述
给定两个整数数组nums1和nums2，以及一个整数k。我们需要找到两个数组中相同长度的连续子数组，使得这两个子数组在最多进行k次元素替换后完全相同。换句话说，我们允许将子数组中最多k个位置的元素替换为任意值，使得替换后的两个子数组完全相同。要求返回满足条件的最长子数组的长度。

解题过程

这个问题是经典最长重复子数组问题的扩展，增加了最多k次替换的灵活性。让我们通过动态规划来系统解决。

步骤1：理解问题核心

• 我们需要在两个数组中找到相同长度的连续子数组
• 允许最多k次替换操作来使子数组相同
• 替换操作可以改变任意位置的元素值
• 目标是找到最长的满足条件的子数组

步骤2：定义状态

我们定义二维DP数组：

• dp[i][j] 表示以nums1的第i-1个元素和nums2的第j-1个元素结尾的子数组，在满足替换限制下的最大匹配长度

但由于我们需要跟踪替换次数，我们需要一个三维DP：

• dp[i][j][m] 表示以nums1[i-1]和nums2[j-1]结尾，使用了m次替换的子数组长度

步骤3：状态转移方程

对于每个位置(i, j)和替换次数m：

1. 如果nums1[i-1] == nums2[j-1]：

   • 不需要替换：dp[i][j][m] = dp[i-1][j-1][m] + 1

2. 如果nums1[i-1] != nums2[j-1]：

   • 如果m > 0（还有替换次数可用）：
     • 使用一次替换：dp[i][j][m] = dp[i-1][j-1][m-1] + 1
   • 否则：
     • 无法匹配：dp[i][j][m] = 0

步骤4：初始化

• 当i=0或j=0时，dp[i][j][m] = 0（空数组）
• 初始时所有位置都设为0

步骤5：寻找最优解
在计算过程中，我们需要记录所有dp[i][j][m]中的最大值，其中m ≤ k。

步骤6：优化空间复杂度
由于三维DP空间复杂度较高，我们可以优化为二维滚动数组。

最终实现

def findLength(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    # dp[i][j] 表示以nums1[i-1]和nums2[j-1]结尾，当前替换次数的最大长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    # diff[i][j] 表示以nums1[i-1]和nums2[j-1]结尾时的替换次数
    diff = [[0] * (n + 1) for _ in range(m + 1)]
    
    max_len = 0
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if nums1[i-1] == nums2[j-1]:
                # 字符相同，直接继承前一个状态
                dp[i][j] = dp[i-1][j-1] + 1
                diff[i][j] = diff[i-1][j-1]
            else:
                # 字符不同，检查是否可以使用替换
                if diff[i-1][j-1] < k:
                    # 使用一次替换
                    dp[i][j] = dp[i-1][j-1] + 1
                    diff[i][j] = diff[i-1][j-1] + 1
                else:
                    # 无法匹配，重置为0
                    dp[i][j] = 0
                    diff[i][j] = 0
            
            max_len = max(max_len, dp[i][j])
    
    return max_len

步骤7：进一步优化

上面的解法虽然正确，但可以进一步优化。我们可以使用滑动窗口+二分查找的方法：

def findLengthOptimized(nums1, nums2, k):
    def check(length):
        # 检查是否存在长度为length的子数组，最多替换k次后相同
        from collections import defaultdict
        
        # 对nums1中所有长度为length的子数组进行哈希
        hash_map = defaultdict(list)
        
        # 计算nums1中所有长度为length的子数组的哈希值
        base, mod = 113, 10**9 + 7
        hash1 = 0
        power = pow(base, length, mod)
        
        for i in range(len(nums1)):
            hash1 = (hash1 * base + nums1[i]) % mod
            if i >= length:
                hash1 = (hash1 - nums1[i-length] * power) % mod
            if i >= length - 1:
                hash_map[hash1].append(i - length + 1)
        
        # 检查nums2
        hash2 = 0
        for i in range(len(nums2)):
            hash2 = (hash2 * base + nums2[i]) % mod
            if i >= length:
                hash2 = (hash2 - nums2[i-length] * power) % mod
            if i >= length - 1:
                if hash2 in hash_map:
                    # 验证是否真的匹配（处理哈希冲突）
                    for start1 in hash_map[hash2]:
                        diff_count = 0
                        match = True
                        for idx in range(length):
                            if nums1[start1 + idx] != nums2[i - length + 1 + idx]:
                                diff_count += 1
                                if diff_count > k:
                                    match = False
                                    break
                        if match:
                            return True
        return False
    
    # 二分查找最长长度
    left, right = 0, min(len(nums1), len(nums2))
    while left < right:
        mid = (left + right + 1) // 2
        if check(mid):
            left = mid
        else:
            right = mid - 1
    
    return left

复杂度分析

• 时间复杂度：O(m×n) 对于DP解法，O((m+n)×log(min(m,n))) 对于优化解法
• 空间复杂度：O(m×n) 对于DP解法，O(m+n) 对于优化解法

这个算法通过允许有限的替换操作，扩展了经典的最长重复子数组问题，在实际应用中具有很好的灵活性。