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

我将为您详细讲解这个线性动态规划问题。这个问题是经典最长重复子数组问题的变种，增加了替换操作的限制。

问题描述

给定两个整数数组nums1和nums2，以及一个整数k。我们需要找到最长的公共子数组，其中允许最多进行k次元素替换操作。也就是说，我们可以将nums1或nums2中的最多k个元素替换为任意值，使得替换后两个数组在某个连续子数组上完全相等。

解题思路

核心思想

这个问题可以通过动态规划结合滑动窗口的思想来解决。我们使用一个二维DP数组，其中dp[i][j]表示以nums1[i]和nums2[j]结尾的子数组，在最多k次替换下的最长公共子数组长度。

状态定义

设dp[i][j]表示以nums1的第i个元素和nums2的第j个元素结尾时，满足条件的最长公共子数组长度。

状态转移方程

对于每个位置(i, j)：

• 如果nums1[i] == nums2[j]，那么dp[i][j] = dp[i-1][j-1] + 1
• 如果nums1[i] != nums2[j]，那么我们可以考虑使用一次替换操作：
  dp[i][j] = dp[i-1][j-1] + 1（如果还有剩余的替换次数）

但是这种直接的方法会使得状态转移变得复杂，因为我们需要跟踪已经使用的替换次数。

更优解法：滑动窗口 + 动态规划

实际上，这个问题更适合用滑动窗口结合前缀和的思想来解决。

算法步骤

1. 预处理：计算两个数组的差异数组diff
2. 滑动窗口：使用双指针维护一个窗口，保证窗口内的差异不超过k
3. 动态记录：记录当前窗口内的替换次数和最长长度

详细实现

让我们通过一个具体的例子来理解：

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

步骤1：理解问题本质

我们实际上是在寻找两个数组中最长的对齐子数组，其中最多有k个位置不匹配。

步骤2：对角线遍历

我们可以沿着对角线方向进行遍历，因为对于每个可能的起始对齐点，我们需要检查从该点开始的最长公共子数组。

def findLength(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    max_len = 0
    
    # 遍历所有可能的对齐方式
    for offset in range(-n + 1, m):
        # 当前对齐下的起始位置
        i = max(offset, 0)
        j = max(-offset, 0)
        
        # 当前窗口内的替换次数和长度
        replacements = 0
        length = 0
        
        # 沿着对角线检查
        while i < m and j < n:
            if nums1[i] == nums2[j]:
                length += 1
            else:
                # 不匹配，使用替换
                if replacements < k:
                    replacements += 1
                    length += 1
                else:
                    # 超过k次替换，重置
                    length = 0
                    replacements = 0
            
            max_len = max(max_len, length)
            i += 1
            j += 1
    
    return max_len

步骤3：优化解法 - 动态规划

上面的方法时间复杂度较高，我们可以用动态规划来优化：

def findLength(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    # dp[i][j] 表示以nums1[i]和nums2[j]结尾的最长公共子数组长度
    # 同时我们需要另一个数组来记录使用的替换次数
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    replacements = [[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
                replacements[i][j] = replacements[i-1][j-1]
            else:
                # 元素不匹配，检查是否可以使用替换
                if replacements[i-1][j-1] < k:
                    dp[i][j] = dp[i-1][j-1] + 1
                    replacements[i][j] = replacements[i-1][j-1] + 1
                else:
                    # 不能使用替换，重新开始
                    dp[i][j] = 0
                    replacements[i][j] = 0
            
            max_len = max(max_len, dp[i][j])
    
    return max_len

步骤4：进一步优化 - 空间优化

由于每个状态只依赖于左上角的状态，我们可以优化空间复杂度：

def findLength(nums1, nums2, k):
    m, n = len(nums1), len(nums2)
    max_len = 0
    
    # 只保存前一行的状态
    prev_dp = [0] * (n + 1)
    prev_replace = [0] * (n + 1)
    
    for i in range(1, m + 1):
        curr_dp = [0] * (n + 1)
        curr_replace = [0] * (n + 1)
        
        for j in range(1, n + 1):
            if nums1[i-1] == nums2[j-1]:
                curr_dp[j] = prev_dp[j-1] + 1
                curr_replace[j] = prev_replace[j-1]
            else:
                if prev_replace[j-1] < k:
                    curr_dp[j] = prev_dp[j-1] + 1
                    curr_replace[j] = prev_replace[j-1] + 1
                else:
                    curr_dp[j] = 0
                    curr_replace[j] = 0
            
            max_len = max(max_len, curr_dp[j])
        
        prev_dp, prev_replace = curr_dp, curr_replace
    
    return max_len

复杂度分析

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

示例验证

让我们用之前的例子验证：
nums1 = [1,2,3,4,5], nums2 = [2,3,1,4,5], k = 1

最长公共子数组是[2,3,4,5]，长度为4（在索引1-4处，只需要替换1次）

这个解法能够有效地找到在最多k次替换下的最长公共子数组，是经典最长重复子数组问题的一个实用扩展。