最长重复子数组的变种：最多允许k次修改的最长重复子数组 题目描述： 给定两个整数数组nums1和nums2，以及一个非负整数k。我们需要找到两个数组中相同长度的连续子数组，使得这两个子数组在最多修改k个元素的情况下完全相同。换句话说，我们可以在任意一个子数组中最多修改k个元素的值，使得修改后的两个子数组完全相同。要求找到满足条件的最长子数组的长度。 解题过程： 问题分析： 我们需要在两个数组中找到两个相同长度的连续子数组，允许最多k次修改使它们相同。这与标准的最长重复子数组问题不同，因为允许一定的差异。 动态规划状态定义： 我们可以使用二维动态规划，但需要记录差异数。定义dp[ i][ j][ d]表示以nums1[ i-1]和nums2[ j-1 ]结尾的子数组，在恰好有d个差异时的最大长度。 状态转移方程： 对于每个位置(i, j)和差异数d： 如果nums1[ i-1] == nums2[ j-1 ]： dp[ i][ j][ d] = dp[ i-1][ j-1][ d ] + 1 如果nums1[ i-1] != nums2[ j-1 ]： dp[ i][ j][ d] = dp[ i-1][ j-1][ d-1 ] + 1 (当d > 0时) 空间优化： 由于dp[ i][ j]只依赖于dp[ i-1][ j-1 ]，我们可以使用二维数组并逆序遍历来优化空间。 具体实现步骤： 初始化二维数组dp，大小为(len(nums2)+1) × (k+1) 遍历nums1的每个元素 对于每个元素，逆序遍历nums2和差异数 根据状态转移方程更新dp值 记录过程中的最大值 时间复杂度：O(n×m×k)，空间复杂度：O(m×k) 边界情况处理： 当k=0时，退化为标准的最长重复子数组问题 当k足够大时，结果就是两个数组中较短的长度 这个算法通过动态规划记录不同差异数下的最长匹配长度，有效地解决了允许有限修改的最长重复子数组问题。