最长重复子数组的变种：最多允许k次修改的最长公共子数组 题目描述 给定两个整数数组nums1和nums2，以及一个整数k。你可以对nums1的最多k个元素进行修改（修改为任意值）。请找出修改后，两个数组中最长的公共子数组的长度。 例如： nums1 = [ 1,2,3,4,5], nums2 = [ 2,3,4,5,6 ], k = 1 输出：4 解释：将nums1中的1修改为6，得到公共子数组[ 2,3,4,5 ]，长度为4 解题过程 步骤1：理解问题本质 这个问题是经典最长公共子数组问题的变种，增加了最多k次修改的灵活性。我们需要找到两个数组中长度最长的相同连续子数组，但允许nums1中最多k个元素与nums2不匹配。 步骤2：定义状态 使用动态规划，定义状态： dp[ i][ j][ m ] 表示以nums1的第i个元素和nums2的第j个元素结尾，且已经使用了m次修改的公共子数组长度 但这样三维DP时间复杂度太高，我们需要优化。 步骤3：优化状态定义 我们可以使用二维DP，但记录额外维度： dp[ i][ j ] 表示以nums1的第i个元素和nums2的第j个元素结尾的公共子数组长度 同时，我们需要记录在当前位置已经使用了多少次修改 实际上，我们可以使用滑动窗口+动态规划的思想： 定义f[ i][ j]为以nums1[ i]和nums2[ j ]结尾的公共子数组，在达到这个位置时已经使用的修改次数 步骤4：核心递推关系 当nums1[ i] == nums2[ j ]时： f[ i][ j] = f[ i-1][ j-1 ] // 不需要额外修改 当nums1[ i] != nums2[ j ]时： f[ i][ j] = f[ i-1][ j-1 ] + 1 // 使用一次修改 但这样还不够，我们需要确保总修改次数不超过k。 步骤5：最终解决方案 我们可以使用二维DP，对于每个位置(i,j)，计算以该位置结尾的公共子数组，在最多使用k次修改的情况下的最大长度。 具体算法： 初始化dp[ i][ j ]为0，表示以i,j结尾的公共子数组长度 初始化mod[ i][ j ]为0，表示达到i,j位置时使用的修改次数 遍历所有i,j： 如果nums1[ i] == nums2[ j ]： dp[ i][ j] = dp[ i-1][ j-1 ] + 1 mod[ i][ j] = mod[ i-1][ j-1 ] 如果nums1[ i] != nums2[ j ]： 如果mod[ i-1][ j-1] < k：// 还可以修改 dp[ i][ j] = dp[ i-1][ j-1 ] + 1 mod[ i][ j] = mod[ i-1][ j-1 ] + 1 否则： dp[ i][ j ] = 0 mod[ i][ j ] = 0 步骤6：边界情况处理 当i=0或j=0时，如果nums1[ i] == nums2[ j]，dp[ i][ j] = 1, mod[ i][ j ] = 0 当i=0或j=0时，如果nums1[ i] != nums2[ j]且k>0，dp[ i][ j] = 1, mod[ i][ j ] = 1 步骤7：时间复杂度优化 上面的解法是O(n²)，对于大数据量可能不够高效。我们可以使用二分答案+滑动窗口的方法来优化到O(n log n)。 二分思路： 二分搜索可能的公共子数组长度L 对于每个长度L，检查是否存在这样的子数组 使用滑动窗口和哈希来快速检查 步骤8：实现细节 在实际实现时，我们还需要考虑： 数组越界检查 空数组处理 k=0时的特殊情况（退化为经典最长公共子数组问题） 这个解法结合了动态规划和修改次数的限制，能够高效地解决问题。