线性动态规划：最长重复子数组的变种——最多允许k次修改的最长重复子数组 题目描述 给定两个整数数组 nums1 和 nums2 ，以及一个非负整数 k 。你需要找到两个数组中相同长度的连续子数组，使得这两个子数组对应位置元素相等的数量最多，但允许最多修改 k 个位置的元素（即允许最多 k 个位置不相等）。求满足条件的最长连续子数组的长度。 解题思路 这个问题是"最长重复子数组"的变种，引入了修改次数限制。我们可以使用动态规划结合滑动窗口的方法来解决。核心思路是：对于每个可能的起始位置，使用双指针维护一个窗口，统计窗口内不相等元素的数量，并通过调整左指针来保证不相等数量不超过 k 。 详细步骤 问题分析 目标：找到两个数组中最长的连续子数组，使得子数组对应位置最多有 k 个元素不相等。 关键点：允许修改 k 次，相当于允许子数组间最多有 k 个位置不匹配。 动态规划结合滑动窗口 对于每个可能的起始偏移，将两个数组对齐，然后使用滑动窗口统计当前窗口内的不匹配数。 具体步骤： a. 枚举 nums1 相对于 nums2 的所有可能起始位置（包括 nums1 向左偏移和 nums2 向左偏移的情况）。 b. 对于每个起始位置，使用双指针 left 和 right 遍历重叠部分。 c. 维护当前窗口内不匹配的元素数量 mismatch 。 d. 当 mismatch > k 时，移动左指针 left 以减少不匹配数，直到 mismatch ≤ k 。 e. 记录每个窗口中满足 mismatch ≤ k 时的最大长度 right - left + 1 。 偏移枚举的具体实现 情况1：固定 nums2 的起始位置为0，将 nums1 从 -len2+1 到 len1-1 偏移。 对于每个偏移值，计算两个数组重叠部分的起始索引和结束索引，确保不越界。 复杂度分析 时间复杂度：O((n + m) * min(n, m))，其中 n 和 m 是数组长度。 空间复杂度：O(1)，仅使用常数变量。 示例演示 以 nums1 = [1, 2, 3, 4], nums2 = [2, 3, 1, 4], k = 1 为例： 当 nums1 偏移1位（即 nums1[1:] 与 nums2 对齐）： 重叠部分： nums1[1]=2 vs nums2[0]=2 （匹配）， nums1[2]=3 vs nums2[1]=3 （匹配）， nums1[3]=4 vs nums2[2]=1 （不匹配，消耗k=1），此时长度为3，满足条件。 最终得到最长长度为3（子数组 [2,3,4] 和 [2,3,1] 最多1处不匹配）。 总结 通过枚举所有可能的对齐方式，并利用滑动窗口控制不匹配数量，可以高效找到最长满足条件的子数组。这种方法将动态规划的思想转化为对每个对齐位置的线性扫描，兼顾了准确性和效率。