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

字数 2815 2025-12-12 18:01:55

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

题目描述
给定两个整数数组 nums1 和 nums2，以及一个非负整数 k。我们需要找到一个最长的公共子数组（连续的子数组），使得在最多替换 k 个元素的前提下，这个子数组在两个数组中是相同的。这里的“替换”是指，我们可以将子数组在 nums1 或 nums2 中对应位置的元素替换成任意值，以使得两个子数组完全相同。目标是最大化子数组的长度。

示例
输入：
nums1 = [1, 2, 3, 4, 5]
nums2 = [5, 2, 3, 4, 1]
k = 1
输出：4
解释：我们可以选择子数组 [2, 3, 4, 5]。在 nums1 中它是索引 1 到 4 的子数组 [2, 3, 4, 5]，在 nums2 中是索引 1 到 4 的子数组 [2, 3, 4, 1]。将 nums2 中的 1 替换为 5（消耗 1 次替换），这两个子数组就相同了。因此最长长度为 4。

解题思路
这个问题是经典的“最长公共子数组”（Longest Common Substring）问题的变种，增加了“最多允许 k 次替换”的灵活性。我们可以用动态规划（DP）来解决，但状态定义需要扩展，以记录当前已经使用的替换次数。

步骤 1：状态定义
定义 dp[i][j][t] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的两个子数组，在使用了恰好 t 次替换的情况下，能够形成的最长公共子数组的长度。
这里 i 和 j 分别从 1 到数组长度，t 从 0 到 k（最多允许替换 k 次）。
注意：子数组是连续的，所以如果当前元素相等，我们可以扩展之前的公共子数组；如果当前元素不等，我们可以通过一次替换来扩展（前提是替换次数足够）。

步骤 2：状态转移方程
我们考虑 nums1[i-1] 和 nums2[j-1] 这两个元素：

如果它们相等，那么我们可以直接从前一个位置 (i-1, j-1) 继承公共子数组的长度，并且不使用替换次数：
dp[i][j][t] = dp[i-1][j-1][t] + 1（其中 t 可以是 0 到 k）。
如果它们不等，但替换次数 t > 0，我们可以消耗一次替换，让它们相等，然后继承前一个位置的状态：
dp[i][j][t] = dp[i-1][j-1][t-1] + 1（其中 t 从 1 到 k）。
如果它们不等且 t = 0，那么以这两个元素结尾的子数组不能匹配，所以 dp[i][j][0] = 0。

另外，无论相等与否，如果前一个位置根本没有公共子数组（即 dp[i-1][j-1][t] 为 0），那么我们不能从那里扩展。但我们的转移方程已经隐含了这个情况，因为如果前一个位置的长度是 0，那么当前长度就是 1（如果消耗替换或相等的话）。实际上，我们应该从“以 i-1 和 j-1 结尾”这个条件来判断是否连续，所以转移方程是正确的。

但注意：如果 i=0 或 j=0，即没有元素，那么长度自然为 0。在 DP 表中，我们用 i=0 和 j=0 的行列来表示空数组的情况，初始化它们为 0。

步骤 3：初始化

当 i=0 或 j=0 时，表示一个数组为空，所以任何公共子数组的长度都是 0。因此对所有 t，dp[0][j][t] = 0，dp[i][0][t] = 0。
其余位置初始化为 0（因为我们要求的是“以 i 和 j 结尾”的长度，如果无法匹配，自然为 0）。

步骤 4：计算顺序
我们需要三层循环：外层循环 i 从 1 到 m（m 是 nums1 长度），中层循环 j 从 1 到 n（n 是 nums2 长度），内层循环 t 从 0 到 k。在计算 dp[i][j][t] 时，我们需要 dp[i-1][j-1][t] 和 dp[i-1][j-1][t-1] 的值，所以必须按顺序计算。

步骤 5：结果提取
我们最终要找到所有 i, j, t 中 dp[i][j][t] 的最大值，因为最优解可能出现在任何位置、使用任何不超过 k 的替换次数。

步骤 6：复杂度分析

时间复杂度：O(m * n * k)，其中 m 和 n 是数组长度。
空间复杂度：O(m * n * k)。但我们可以用滚动数组优化空间到 O(n * k) 或 O(m * k)，因为我们只依赖于上一行和上一列的状态（具体来说，只依赖于 (i-1, j-1) 的状态，所以可以只保留上一行，但需要小心处理 t 的遍历顺序）。

步骤 7：例子推导
以示例为例，nums1 = [1, 2, 3, 4, 5]，nums2 = [5, 2, 3, 4, 1]，k = 1。
我们可以手动推导一小部分：

当 i=2, j=2，即 nums1[1]=2 和 nums2[1]=2 相等，所以 dp[2][2][0] = dp[1][1][0] + 1。而 dp[1][1][0] 表示以 nums1[0]=1 和 nums2[0]=5 结尾，它们不等且 t=0，所以 dp[1][1][0]=0，因此 dp[2][2][0] = 1。
同样，如果我们允许一次替换，在 i=1, j=1 时，nums1[0]=1 和 nums2[0]=5 不等，但可以用一次替换让它们相等，所以 dp[1][1][1] = dp[0][0][0] + 1 = 1。

最终，我们会在 i=5, j=4 等位置得到长度 4 的解。

步骤 8：边界情况

如果 k 大于等于 min(m, n)，那么我们可以替换所有不匹配的元素，所以答案就是 min(m, n)（因为公共子数组最多是较短的数组长度）。
如果 k=0，那么退化为标准的最长公共子数组问题。
如果数组为空，那么答案是 0。

步骤 9：实现要点
在实现时，我们可以用二维 DP 数组，其中 dp[j][t] 表示当前行以 nums2[j-1] 结尾、使用 t 次替换的最长公共子数组长度。但为了从 (i-1, j-1) 转移，我们需要保存上一行的值，所以可以用一个临时数组保存 dp[i-1][j-1][t] 的值，或者用两个二维数组分别表示当前行和上一行。

总结
这个问题的核心是在经典的最长公共子数组动态规划上增加了一个替换次数的维度。状态转移方程考虑了当前元素相等和不等两种情况，并通过消耗替换次数来处理不相等的情况。最终遍历整个 DP 表取最大值即可得到答案。

最长重复子数组的变种：最多允许k次替换的最长公共子数组题目描述给定两个整数数组 nums1 和 nums2 ，以及一个非负整数 k 。我们需要找到一个最长的公共子数组（连续的子数组），使得在最多替换 k 个元素的前提下，这个子数组在两个数组中是相同的。这里的“替换”是指，我们可以将子数组在 nums1 或 nums2 中对应位置的元素替换成任意值，以使得两个子数组完全相同。目标是最大化子数组的长度。示例输入： nums1 = [1, 2, 3, 4, 5] nums2 = [5, 2, 3, 4, 1] k = 1 输出： 4 解释：我们可以选择子数组 [2, 3, 4, 5] 。在 nums1 中它是索引 1 到 4 的子数组 [2, 3, 4, 5] ，在 nums2 中是索引 1 到 4 的子数组 [2, 3, 4, 1] 。将 nums2 中的 1 替换为 5（消耗 1 次替换），这两个子数组就相同了。因此最长长度为 4。解题思路这个问题是经典的“最长公共子数组”（Longest Common Substring）问题的变种，增加了“最多允许 k 次替换”的灵活性。我们可以用动态规划（DP）来解决，但状态定义需要扩展，以记录当前已经使用的替换次数。步骤 1：状态定义定义 dp[i][j][t] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的两个子数组，在使用了恰好 t 次替换的情况下，能够形成的最长公共子数组的长度。这里 i 和 j 分别从 1 到数组长度， t 从 0 到 k（最多允许替换 k 次）。注意：子数组是连续的，所以如果当前元素相等，我们可以扩展之前的公共子数组；如果当前元素不等，我们可以通过一次替换来扩展（前提是替换次数足够）。步骤 2：状态转移方程我们考虑 nums1[i-1] 和 nums2[j-1] 这两个元素：如果它们相等，那么我们可以直接从前一个位置 (i-1, j-1) 继承公共子数组的长度，并且不使用替换次数： dp[i][j][t] = dp[i-1][j-1][t] + 1 （其中 t 可以是 0 到 k）。如果它们不等，但替换次数 t > 0 ，我们可以消耗一次替换，让它们相等，然后继承前一个位置的状态： dp[i][j][t] = dp[i-1][j-1][t-1] + 1 （其中 t 从 1 到 k）。如果它们不等且 t = 0 ，那么以这两个元素结尾的子数组不能匹配，所以 dp[i][j][0] = 0 。另外，无论相等与否，如果前一个位置根本没有公共子数组（即 dp[i-1][j-1][t] 为 0），那么我们不能从那里扩展。但我们的转移方程已经隐含了这个情况，因为如果前一个位置的长度是 0，那么当前长度就是 1（如果消耗替换或相等的话）。实际上，我们应该从“以 i-1 和 j-1 结尾”这个条件来判断是否连续，所以转移方程是正确的。但注意：如果 i=0 或 j=0 ，即没有元素，那么长度自然为 0。在 DP 表中，我们用 i=0 和 j=0 的行列来表示空数组的情况，初始化它们为 0。步骤 3：初始化当 i=0 或 j=0 时，表示一个数组为空，所以任何公共子数组的长度都是 0。因此对所有 t ， dp[0][j][t] = 0 ， dp[i][0][t] = 0 。其余位置初始化为 0（因为我们要求的是“以 i 和 j 结尾”的长度，如果无法匹配，自然为 0）。步骤 4：计算顺序我们需要三层循环：外层循环 i 从 1 到 m （ m 是 nums1 长度），中层循环 j 从 1 到 n （ n 是 nums2 长度），内层循环 t 从 0 到 k 。在计算 dp[i][j][t] 时，我们需要 dp[i-1][j-1][t] 和 dp[i-1][j-1][t-1] 的值，所以必须按顺序计算。步骤 5：结果提取我们最终要找到所有 i, j, t 中 dp[i][j][t] 的最大值，因为最优解可能出现在任何位置、使用任何不超过 k 的替换次数。步骤 6：复杂度分析时间复杂度：O(m * n * k)，其中 m 和 n 是数组长度。空间复杂度：O(m * n * k)。但我们可以用滚动数组优化空间到 O(n * k) 或 O(m * k)，因为我们只依赖于上一行和上一列的状态（具体来说，只依赖于 (i-1, j-1) 的状态，所以可以只保留上一行，但需要小心处理 t 的遍历顺序）。步骤 7：例子推导以示例为例， nums1 = [1, 2, 3, 4, 5] ， nums2 = [5, 2, 3, 4, 1] ， k = 1 。我们可以手动推导一小部分：当 i=2, j=2，即 nums1[ 1]=2 和 nums2[ 1]=2 相等，所以 dp[ 2][ 2][ 0] = dp[ 1][ 1][ 0] + 1。而 dp[ 1][ 1][ 0] 表示以 nums1[ 0]=1 和 nums2[ 0]=5 结尾，它们不等且 t=0，所以 dp[ 1][ 1][ 0]=0，因此 dp[ 2][ 2][ 0 ] = 1。同样，如果我们允许一次替换，在 i=1, j=1 时，nums1[ 0]=1 和 nums2[ 0]=5 不等，但可以用一次替换让它们相等，所以 dp[ 1][ 1][ 1] = dp[ 0][ 0][ 0 ] + 1 = 1。最终，我们会在 i=5, j=4 等位置得到长度 4 的解。步骤 8：边界情况如果 k 大于等于 min(m, n)，那么我们可以替换所有不匹配的元素，所以答案就是 min(m, n)（因为公共子数组最多是较短的数组长度）。如果 k=0，那么退化为标准的最长公共子数组问题。如果数组为空，那么答案是 0。步骤 9：实现要点在实现时，我们可以用二维 DP 数组，其中 dp[j][t] 表示当前行以 nums2[j-1] 结尾、使用 t 次替换的最长公共子数组长度。但为了从 (i-1, j-1) 转移，我们需要保存上一行的值，所以可以用一个临时数组保存 dp[i-1][j-1][t] 的值，或者用两个二维数组分别表示当前行和上一行。总结这个问题的核心是在经典的最长公共子数组动态规划上增加了一个替换次数的维度。状态转移方程考虑了当前元素相等和不等两种情况，并通过消耗替换次数来处理不相等的情况。最终遍历整个 DP 表取最大值即可得到答案。