带限制的最长重复子数组（限制子数组长度至少为L且最多允许k次不匹配）
字数 6152 2025-12-24 03:53:28

带限制的最长重复子数组（限制子数组长度至少为L且最多允许k次不匹配）

这是一个线性动态规划的进阶题目，我们将循序渐进地讲解它。

题目描述

给定两个整数数组 nums1 和 nums2，以及两个非负整数 L 和 k。要求找出最长的公共子数组（连续子序列），使得：

  1. 该公共子数组的长度至少为 L。
  2. 在子数组对应位置上，允许最多 k 个位置的元素不相同（即最多允许 k 次不匹配）。
  3. 输出这个满足条件的公共子数组的最大可能长度。

示例

  • nums1 = [1, 2, 3, 4, 5]
  • nums2 = [2, 3, 1, 4, 5]
  • L = 2, k = 1
  • 解释：最长公共子数组可以是 [2, 3, 4, 5]（在 nums1 中为下标 1,2,3,4；在 nums2 中为下标 0,1,3,4）。对比两个子数组：[2,3,4,5] vs [2,3,4,5]，完全匹配，长度为4。另一个候选是 [1,2,3]（nums1[0:2] 和 nums2[2:4] 为 [1,2] vs [1,4]，有1处不匹配），但长度3小于4。所以答案为4。

这个题目综合了最长公共子数组（经典DP）与带容错的最长公共子串（允许不匹配）的思想，并增加了最小长度约束。我们将用动态规划来解决它。

解题思路

1. 问题拆解

我们需要在两个数组中找到一个连续的片段（子数组），使得它们尽可能长，同时：

  • 长度 ≥ L。
  • 对应位置上不同的元素数量 ≤ k。

核心难点：如何高效地记录“从某个位置开始对齐时，已经产生了多少不匹配”。

2. 基础动态规划定义

一个直观的想法是，用 dp[i][j] 表示“以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组的长度”。但这样无法直接处理不匹配限制。

改进：我们定义 dp[i][j][t]，表示“以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组的长度，并且该子数组中恰好有 t 个不匹配的位置”。但这样空间复杂度会很高（O(n * m * k)），且难以处理“至少L长度”的条件。

更高效的方法：采用二维DP + 不匹配计数滚动数组。

3. 状态定义

我们定义 dp[i][j] 表示：以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组中，最少的不匹配数量。
注意：这里“公共子数组”必须是连续的，所以如果 nums1[i-1] != nums2[j-1]，那么以它们结尾的子数组就不成立？不对——因为我们允许不匹配，所以即使末尾两个元素不同，子数组也可能成立，只要不匹配数量不超过k。

但这样定义的话，dp[i][j] 仅仅记录了“最少不匹配数量”，我们还需要知道对应的子数组长度。因此我们可以用另一个数组 len[i][j] 来记录对应的子数组长度。

更简洁的方法：我们不将不匹配数量作为状态值，而是作为约束条件，用递推关系来隐含地计算它。

4. 递推关系设计（核心）

让我们考虑两个数组的当前位置 i（nums1 的第 i-1 个元素）和 j（nums2 的第 j-1 个元素）。

设 f[i][j] 表示：以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组的长度（注意这里“公共子数组”是允许不匹配的，但我们必须知道这个子数组里有多少不匹配）。

为了知道不匹配数量，我们同时维护一个不匹配计数 cnt[i][j]，表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组中，不匹配的元素个数。

递推关系：

  • 如果 nums1[i-1] == nums2[j-1]，那么我们可以从 f[i-1][j-1] 扩展过来：
    • f[i][j] = f[i-1][j-1] + 1
    • cnt[i][j] = cnt[i-1][j-1] （没有新增不匹配）
  • 如果 nums1[i-1] != nums2[j-1]，那么我们依然可以尝试扩展，但会增加一个不匹配：
    • f[i][j] = f[i-1][j-1] + 1
    • cnt[i][j] = cnt[i-1][j-1] + 1

但是，如果 cnt[i][j] > k，那么这个子数组就不合法了。怎么办？我们需要回溯缩短子数组，直到不匹配数 ≤ k。

所以，仅仅从 (i-1, j-1) 转移是不够的，我们需要知道：从当前位置 (i, j) 往前推，最多能延伸多长的子数组，使得不匹配数 ≤ k。

5. 优化：双指针（滑动窗口）思想

我们固定一对起点偏移量 d = i - j（即两个数组的起始下标差），然后在每个偏移量下，用双指针扫描。
具体来说，对于每个 d，我们考虑 nums1 从某个位置开始，nums2 从 某个位置-d 开始，然后向右同步扩展，并维护当前窗口内的不匹配数。当不匹配数 > k 时，左端点右移，直到不匹配数 ≤ k。在过程中，如果窗口长度 ≥ L，我们就更新答案。

但是这种方法需要枚举所有可能的偏移量 d，其范围是 [-(m-1), n-1]，复杂度约为 O((n+m) * min(n,m))，在数组长度较大时可能较慢。

6. 最终高效DP方法

我们可以用 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组中，不匹配的数量。
但为了快速得到长度，我们实际上需要二分答案。

二分答案思路：

  1. 假设我们要判断是否存在长度为 len 的公共子数组，满足不匹配 ≤ k 且长度 ≥ L。
  2. 如果 len < L，显然不满足最小长度条件，所以二分的下界是 L，上界是 min(n, m)。
  3. 对于某个猜测的长度 mid，我们检查是否存在这样的子数组。

如何检查是否存在长度为 mid 的公共子数组（允许 ≤ k 个不匹配）？

  • 我们可以枚举所有可能的起始位置 i 在 nums1 中，对应的 j 在 nums2 中，使得子数组长度为 mid。
  • 对于每个对齐的起始位置，计算两个子数组的不匹配数（对应位置不同的个数）。
  • 如果不匹配数 ≤ k，则找到答案。

但是直接枚举起点复杂度高。我们可以用前缀和优化来快速计算不匹配数：

  • 对于每个对齐的起始位置 (i, j)，长度为 mid，不匹配数 = 对应位置不同的数量。
  • 我们可以预处理一个二维差分或直接扫描，但更简单的是：
    用 diff[i][j] = (nums1[i] != nums2[j] ? 1 : 0)，然后对于每个 d = i - j，我们固定 d，然后计算 diff 在斜线上的前缀和，用滑动窗口求区间和 ≤ k。

7. 动态规划斜线前缀和

设 n = len(nums1), m = len(nums2)。
对于每个差值 d（范围 -(m-1) 到 n-1），我们定义数组 arr，其中 arr[p] = (nums1[p] != nums2[p-d] ? 1 : 0)，这里 p 的取值范围是使得下标合法的范围。

然后我们在 arr 上使用滑动窗口，找长度 ≥ L 且区间和 ≤ k 的最长连续子数组。
注意：arr 的长度可能小于 min(n,m)，但没关系。

8. 算法步骤

  1. 初始化答案 ans = 0。
  2. 枚举差值 d 从 -(m-1) 到 n-1：
    • 确定起点范围：i 从 max(0, d) 到 min(n-1, m-1+d)。
    • 构造数组 arr，长度为 len_arr，其中 arr[t] = (nums1[i_start + t] != nums2[i_start + t - d] ? 1 : 0)。
    • 在 arr 上执行滑动窗口：
      • 左指针 l = 0，当前窗口不匹配数 sum_mismatch = 0。
      • 右指针 r 从 0 到 len_arr-1：
        • sum_mismatch += arr[r]
        • 当 sum_mismatch > k 时，移动左指针 l 直到 sum_mismatch ≤ k（同时减少 sum_mismatch 减去 arr[l]）。
        • 此时窗口长度 win_len = r - l + 1，如果 win_len ≥ L，则更新 ans = max(ans, win_len)。
  3. 返回 ans。

9. 复杂度分析

  • 枚举 d 的个数：O(n + m)。
  • 每个 d 对应的 arr 长度最多 min(n, m)。
  • 每个 d 的滑动窗口扫描是线性的。
  • 总复杂度：O((n+m) * min(n,m))，在 n 和 m 同数量级时约 O(n^2)。

10. 举例说明

假设：

  • nums1 = [1,2,3,4,5]
  • nums2 = [2,3,1,4,5]
  • L = 2, k = 1

枚举 d = 0：

  • 对齐位置：i 和 j 相同下标。
  • arr 比较 nums1[i] 和 nums2[i]：
    • i=0: 1 vs 2 → 1
    • i=1: 2 vs 3 → 1
    • i=2: 3 vs 1 → 1
    • i=3: 4 vs 4 → 0
    • i=4: 5 vs 5 → 0
  • arr = [1,1,1,0,0]
  • 滑动窗口找最长子数组使得和 ≤ 1 且长度 ≥ 2：
    • 最长窗口可能是 [0,0]（对应下标 3,4），长度2，和=0，满足。
    • 所以长度2可行。但我们找更长的：如果窗口包含前面的1，和会>1，除非只包含一个1。比如 [1,0]（和=1）长度2可行，但长度不够大。
    • 最终得到该 d 下的最长满足条件的窗口长度 = 2。

枚举 d = 1：

  • 对齐：nums1[i] 与 nums2[i-1] 比较。
  • i 从1到4：
    • i=1: 2 vs 2 → 0
    • i=2: 3 vs 3 → 0
    • i=3: 4 vs 1 → 1
    • i=4: 5 vs 4 → 1
  • arr = [0,0,1,1]
  • 滑动窗口：
    • 最长窗口 [0,0]（前两个）和=0，长度=2。
    • 加上第三个元素，和=1，长度=3，仍满足 ≤1。
    • 加上第四个元素，和=2 >1，左移直到和≤1，窗口变为 [1]（第三个元素）或 [0,0,1] 等。
    • 最长窗口长度=3（对应 [0,0,1]），满足长度≥2且不匹配=1。这就是我们找到的 [2,3,4]（nums1[1:3]）和 [2,3,1]（nums2[0:2]），有一个不匹配。
    • 但这个长度3小于我们之前找到的4吗？注意这个窗口长度是3，但对应原数组的子数组长度就是3（因为 d 固定时，窗口长度就是公共子数组长度）。

继续枚举 d，最终会发现 d = -1 时可能得到更长结果：

  • d = -1：nums1[i] 与 nums2[i+1] 比较。
  • i 从0到3：
    • i=0: 1 vs 3 → 1
    • i=1: 2 vs 1 → 1
    • i=2: 3 vs 4 → 1
    • i=3: 4 vs 5 → 1
  • 全是1，没有长度≥2且和≤1的窗口。

但是否漏掉了更优解？我们之前示例说答案是4，对应 d = -3（nums1[1:4] 与 nums2[0:3]）：

  • d = -3：nums1[i] 与 nums2[i+3] 比较。
  • i 从0到1（因为 nums2 下标 i+3 ≤4）：
    • i=0: 1 vs 4 → 1
    • i=1: 2 vs 5 → 1
  • 长度只有2，和=2>1，不满足。

等等，示例中的 [2,3,4,5] 在 nums1[1:4]（下标1,2,3,4）和 nums2[0:3]（下标0,1,3,4）对齐时，差值 d = 1（因为 nums1 下标1对应 nums2 下标0，d=1）。我们检查 d=1 时的情况：

  • 前面 d=1 时我们只比较了 i=1..4，但实际公共子数组长度4对应 i=1..4 与 j=0..3。
  • 对于 i=1..4（nums1[1]到nums1[4]）和 j=0..3（nums2[0]到nums2[3]）：
    • 对比： (2,2)=0, (3,3)=0, (4,1)=1, (5,4)=1 → 不匹配数=2。
    • 但允许 k=1，所以这个对齐不满足条件。

这说明我之前的示例有误！实际上 [2,3,4,5] 与 [2,3,4,5] 完全匹配，对应 nums1[1:4] 和 nums2[0:3] 时，应该是 (2,2)=0, (3,3)=0, (4,4)=0, (5,5)=0，不匹配数=0。这要求 nums2 的下标是 0,1,3,4？不，这不对应连续子数组，因为下标 0,1,3,4 不连续。所以这个例子中，连续公共子数组 [2,3,4,5] 必须在 nums2 中也连续，但 nums2 是 [2,3,1,4,5]，连续子数组 [2,3,4,5] 不存在。所以示例中的答案4是错误的。

我们修正示例：
nums1 = [1,2,3,4,5]
nums2 = [2,3,4,5,1]
L=2, k=1
则 [2,3,4,5] 在 nums1[1:4] 和 nums2[0:3] 完全匹配，长度4，满足。

对于这个修正后的例子，枚举 d=1（nums1[i] 与 nums2[i-1]）：

  • i=1..4：对比 (2,2)=0, (3,3)=0, (4,4)=0, (5,5)=0 → arr=[0,0,0,0]
  • 滑动窗口：最长窗口长度=4，不匹配数=0，满足条件，更新 ans=4。

11. 最终算法总结

  1. 初始化 ans = 0。
  2. 对于每个差值 d 从 -(m-1) 到 n-1：
    • 确定 i 的范围：i_start = max(0, d), i_end = min(n-1, m-1+d)。
    • 构造 arr 长度为 len_arr = i_end - i_start + 1，arr[t] = (nums1[i_start+t] != nums2[i_start+t-d] ? 1 : 0)。
    • 在 arr 上运行滑动窗口：维护窗口内不匹配数 sum_mismatch，当 sum_mismatch > k 时左移左指针，当窗口长度 ≥ L 时更新 ans。
  3. 返回 ans。

通过以上步骤，我们就能在 O((n+m)*min(n,m)) 时间内解决这个带限制的最长重复子数组问题。

带限制的最长重复子数组（限制子数组长度至少为L且最多允许k次不匹配） 这是一个线性动态规划的进阶题目，我们将循序渐进地讲解它。 题目描述 给定两个整数数组 nums1 和 nums2 ，以及两个非负整数 L 和 k 。要求找出 最长 的公共子数组（连续子序列），使得： 该公共子数组的 长度至少为 L 。 在子数组对应位置上，允许 最多 k 个位置 的元素不相同（即最多允许 k 次不匹配）。 输出这个满足条件的公共子数组的最大可能长度。 示例 nums1 = [1, 2, 3, 4, 5] nums2 = [2, 3, 1, 4, 5] L = 2, k = 1 解释：最长公共子数组可以是 [2, 3, 4, 5] （在 nums1 中为下标 1,2,3,4 ；在 nums2 中为下标 0,1,3,4 ）。对比两个子数组： [2,3,4,5] vs [2,3,4,5] ，完全匹配，长度为4。另一个候选是 [1,2,3] （ nums1[0:2] 和 nums2[2:4] 为 [1,2] vs [1,4] ，有1处不匹配），但长度3小于4。所以答案为4。 这个题目综合了 最长公共子数组 （经典DP）与 带容错的最长公共子串 （允许不匹配）的思想，并增加了 最小长度约束 。我们将用动态规划来解决它。 解题思路 1. 问题拆解 我们需要在两个数组中找到一个连续的片段（子数组），使得它们尽可能长，同时： 长度 ≥ L。 对应位置上不同的元素数量 ≤ k。 核心难点 ：如何高效地记录“从某个位置开始对齐时，已经产生了多少不匹配”。 2. 基础动态规划定义 一个直观的想法是，用 dp[i][j] 表示“以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组的长度”。但这样无法直接处理不匹配限制。 改进：我们定义 dp[i][j][t] ，表示“以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组的长度，并且该子数组中恰好有 t 个不匹配的位置”。但这样空间复杂度会很高（O(n * m * k)），且难以处理“至少L长度”的条件。 更高效的方法：采用 二维DP + 不匹配计数滚动数组 。 3. 状态定义 我们定义 dp[i][j] 表示： 以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组中，最少的不匹配数量 。 注意：这里“公共子数组”必须是连续的，所以如果 nums1[i-1] != nums2[j-1] ，那么以它们结尾的子数组就不成立？不对——因为我们允许不匹配，所以即使末尾两个元素不同，子数组也可能成立，只要不匹配数量不超过k。 但这样定义的话， dp[i][j] 仅仅记录了“最少不匹配数量”，我们还需要知道对应的子数组长度。因此我们可以用另一个数组 len[i][j] 来记录对应的子数组长度。 更简洁的方法：我们 不将不匹配数量作为状态值，而是作为约束条件 ，用递推关系来隐含地计算它。 4. 递推关系设计（核心） 让我们考虑两个数组的当前位置 i （ nums1 的第 i-1 个元素）和 j （ nums2 的第 j-1 个元素）。 设 f[i][j] 表示： 以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组的长度 （注意这里“公共子数组”是 允许不匹配 的，但我们必须知道这个子数组里有多少不匹配）。 为了知道不匹配数量，我们同时维护一个 不匹配计数 cnt[i][j] ，表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组中，不匹配的元素个数。 递推关系： 如果 nums1[i-1] == nums2[j-1] ，那么我们可以从 f[i-1][j-1] 扩展过来： f[i][j] = f[i-1][j-1] + 1 cnt[i][j] = cnt[i-1][j-1] （没有新增不匹配） 如果 nums1[i-1] != nums2[j-1] ，那么我们依然可以尝试扩展，但会增加一个不匹配： f[i][j] = f[i-1][j-1] + 1 cnt[i][j] = cnt[i-1][j-1] + 1 但是，如果 cnt[i][j] > k ，那么这个子数组就不合法了。怎么办？我们需要 回溯缩短子数组 ，直到不匹配数 ≤ k。 所以，仅仅从 (i-1, j-1) 转移是不够的，我们需要知道：从当前位置 (i, j) 往前推，最多能延伸多长的子数组，使得不匹配数 ≤ k。 5. 优化：双指针（滑动窗口）思想 我们固定一对起点偏移量 d = i - j （即两个数组的起始下标差），然后在每个偏移量下，用双指针扫描。 具体来说，对于每个 d ，我们考虑 nums1 从某个位置开始， nums2 从 某个位置-d 开始，然后向右同步扩展，并维护当前窗口内的不匹配数。当不匹配数 > k 时，左端点右移，直到不匹配数 ≤ k。在过程中，如果窗口长度 ≥ L，我们就更新答案。 但是这种方法需要枚举所有可能的偏移量 d ，其范围是 [-(m-1), n-1] ，复杂度约为 O((n+m) * min(n,m)) ，在数组长度较大时可能较慢。 6. 最终高效DP方法 我们可以用 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组中，不匹配的数量 。 但为了快速得到长度，我们实际上需要 二分答案 。 二分答案思路 ： 假设我们要判断是否存在长度为 len 的公共子数组，满足不匹配 ≤ k 且长度 ≥ L。 如果 len < L ，显然不满足最小长度条件，所以二分的下界是 L ，上界是 min(n, m) 。 对于某个猜测的长度 mid ，我们检查是否存在这样的子数组。 如何检查是否存在长度为 mid 的公共子数组（允许 ≤ k 个不匹配）？ 我们可以枚举所有可能的起始位置 i 在 nums1 中，对应的 j 在 nums2 中，使得子数组长度为 mid 。 对于每个对齐的起始位置，计算两个子数组的不匹配数（对应位置不同的个数）。 如果不匹配数 ≤ k，则找到答案。 但是直接枚举起点复杂度高。我们可以用 前缀和优化 来快速计算不匹配数： 对于每个对齐的起始位置 (i, j) ，长度为 mid ，不匹配数 = 对应位置不同的数量。 我们可以预处理一个二维差分或直接扫描，但更简单的是： 用 diff[i][j] = (nums1[i] != nums2[j] ? 1 : 0) ，然后对于每个 d = i - j ，我们固定 d ，然后计算 diff 在斜线上的前缀和，用滑动窗口求区间和 ≤ k。 7. 动态规划斜线前缀和 设 n = len(nums1) , m = len(nums2) 。 对于每个差值 d （范围 -(m-1) 到 n-1 ），我们定义数组 arr ，其中 arr[p] = (nums1[p] != nums2[p-d] ? 1 : 0) ，这里 p 的取值范围是使得下标合法的范围。 然后我们在 arr 上使用滑动窗口，找长度 ≥ L 且区间和 ≤ k 的最长连续子数组。 注意： arr 的长度可能小于 min(n,m) ，但没关系。 8. 算法步骤 初始化答案 ans = 0 。 枚举差值 d 从 -(m-1) 到 n-1 ： 确定起点范围： i 从 max(0, d) 到 min(n-1, m-1+d) 。 构造数组 arr ，长度为 len_arr ，其中 arr[t] = (nums1[i_start + t] != nums2[i_start + t - d] ? 1 : 0) 。 在 arr 上执行滑动窗口： 左指针 l = 0 ，当前窗口不匹配数 sum_mismatch = 0 。 右指针 r 从 0 到 len_arr-1 ： sum_mismatch += arr[r] 当 sum_mismatch > k 时，移动左指针 l 直到 sum_mismatch ≤ k （同时减少 sum_mismatch 减去 arr[l] ）。 此时窗口长度 win_len = r - l + 1 ，如果 win_len ≥ L ，则更新 ans = max(ans, win_len) 。 返回 ans 。 9. 复杂度分析 枚举 d 的个数： O(n + m) 。 每个 d 对应的 arr 长度最多 min(n, m) 。 每个 d 的滑动窗口扫描是线性的。 总复杂度： O((n+m) * min(n,m)) ，在 n 和 m 同数量级时约 O(n^2) 。 10. 举例说明 假设： nums1 = [1,2,3,4,5] nums2 = [2,3,1,4,5] L = 2, k = 1 枚举 d = 0 ： 对齐位置： i 和 j 相同下标。 arr 比较 nums1[i] 和 nums2[i] ： i=0 : 1 vs 2 → 1 i=1 : 2 vs 3 → 1 i=2 : 3 vs 1 → 1 i=3 : 4 vs 4 → 0 i=4 : 5 vs 5 → 0 arr = [1,1,1,0,0] 滑动窗口找最长子数组使得和 ≤ 1 且长度 ≥ 2： 最长窗口可能是 [0,0] （对应下标 3,4），长度2，和=0，满足。 所以长度2可行。但我们找更长的：如果窗口包含前面的1，和会>1，除非只包含一个1。比如 [1,0] （和=1）长度2可行，但长度不够大。 最终得到该 d 下的最长满足条件的窗口长度 = 2。 枚举 d = 1 ： 对齐： nums1[i] 与 nums2[i-1] 比较。 i 从1到4： i=1: 2 vs 2 → 0 i=2: 3 vs 3 → 0 i=3: 4 vs 1 → 1 i=4: 5 vs 4 → 1 arr = [0,0,1,1] 滑动窗口： 最长窗口 [0,0] （前两个）和=0，长度=2。 加上第三个元素，和=1，长度=3，仍满足 ≤1。 加上第四个元素，和=2 >1，左移直到和≤1，窗口变为 [1] （第三个元素）或 [0,0,1] 等。 最长窗口长度=3（对应 [0,0,1] ），满足长度≥2且不匹配=1。这就是我们找到的 [2,3,4] （nums1[ 1:3]）和 [2,3,1] （nums2[ 0:2 ]），有一个不匹配。 但这个长度3小于我们之前找到的4吗？注意这个窗口长度是3，但对应原数组的子数组长度就是3（因为 d 固定时，窗口长度就是公共子数组长度）。 继续枚举 d ，最终会发现 d = -1 时可能得到更长结果： d = -1 ： nums1[i] 与 nums2[i+1] 比较。 i 从0到3： i=0: 1 vs 3 → 1 i=1: 2 vs 1 → 1 i=2: 3 vs 4 → 1 i=3: 4 vs 5 → 1 全是1，没有长度≥2且和≤1的窗口。 但是否漏掉了更优解？我们之前示例说答案是4，对应 d = -3 （ nums1[1:4] 与 nums2[0:3] ）： d = -3 ： nums1[i] 与 nums2[i+3] 比较。 i 从0到1（因为 nums2 下标 i+3 ≤4）： i=0: 1 vs 4 → 1 i=1: 2 vs 5 → 1 长度只有2，和=2>1，不满足。 等等，示例中的 [2,3,4,5] 在 nums1[1:4] （下标1,2,3,4）和 nums2[0:3] （下标0,1,3,4）对齐时，差值 d = 1 （因为 nums1 下标1对应 nums2 下标0，d=1）。我们检查 d=1 时的情况： 前面 d=1 时我们只比较了 i=1..4 ，但实际公共子数组长度4对应 i=1..4 与 j=0..3 。 对于 i=1..4 （nums1[ 1]到nums1[ 4]）和 j=0..3 （nums2[ 0]到nums2[ 3 ]）： 对比： (2,2)=0, (3,3)=0, (4,1)=1, (5,4)=1 → 不匹配数=2。 但允许 k=1，所以这个对齐不满足条件。 这说明我之前的示例有误！实际上 [2,3,4,5] 与 [2,3,4,5] 完全匹配，对应 nums1[1:4] 和 nums2[0:3] 时，应该是 (2,2)=0, (3,3)=0, (4,4)=0, (5,5)=0 ，不匹配数=0。这要求 nums2 的下标是 0,1,3,4 ？不，这不对应连续子数组，因为下标 0,1,3,4 不连续。所以这个例子中，连续公共子数组 [2,3,4,5] 必须在 nums2 中也连续，但 nums2 是 [2,3,1,4,5] ，连续子数组 [2,3,4,5] 不存在。所以示例中的答案4是错误的。 我们修正示例： nums1 = [1,2,3,4,5] nums2 = [2,3,4,5,1] L=2, k=1 则 [2,3,4,5] 在 nums1[1:4] 和 nums2[0:3] 完全匹配，长度4，满足。 对于这个修正后的例子，枚举 d=1 （ nums1[i] 与 nums2[i-1] ）： i=1..4：对比 (2,2)=0, (3,3)=0, (4,4)=0, (5,5)=0 → arr=[0,0,0,0] 滑动窗口：最长窗口长度=4，不匹配数=0，满足条件，更新 ans=4。 11. 最终算法总结 初始化 ans = 0。 对于每个差值 d 从 -(m-1) 到 n-1： 确定 i 的范围：i_ start = max(0, d), i_ end = min(n-1, m-1+d)。 构造 arr 长度为 len_ arr = i_ end - i_ start + 1，arr[ t] = (nums1[ i_ start+t] != nums2[ i_ start+t-d ] ? 1 : 0)。 在 arr 上运行滑动窗口：维护窗口内不匹配数 sum_ mismatch，当 sum_ mismatch > k 时左移左指针，当窗口长度 ≥ L 时更新 ans。 返回 ans。 通过以上步骤，我们就能在 O((n+m)* min(n,m)) 时间内解决这个带限制的最长重复子数组问题。