LeetCode 718 - 最长重复子数组

LeetCode 718 - 最长重复子数组 是一个典型的数组和字符串问题，适合考察动态规划、滑动窗口和二分查找等多种编程能力。掌握其多种解法及变体能够有效提高处理字符串和数组算法的能力。

---

题目描述

• 输入: 两个整数数组 nums1 和 nums2。
• 输出: 两个数组中存在的最长的连续重复子数组的长度。
• 要求: 时间复杂度尽可能优化。

示例

输入: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出: 3
解释: 最长的重复子数组是 [3,2,1], 长度为 3。

---

解法分析及实现

解法 1：二维动态规划

思路

• 定义 dp[i][j] 表示：
  • 以下标 i-1（对于 nums1）结尾的子数组和以下标 j-1（对于 nums2）结尾的子数组的最长公共子数组长度。
• 状态转移方程：
  • 如果 nums1[i-1] == nums2[j-1]:

    dp[i][j] = dp[i-1][j-1] + 1
    

  • 否则：

    dp[i][j] = 0
    

• 初始化：
  • dp[i][0] = 0 (空序列和任何序列无公共子数组)。
  • dp[0][j] = 0 (空序列和任何序列无公共子数组)。
• 最终答案：
  • 遍历所有的 dp[i][j]，取最大值。

模板代码

class Solution {public int findLength(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;int[][] dp = new int[m + 1][n + 1];int maxLength = 0;// 动态规划填表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;maxLength = Math.max(maxLength, dp[i][j]);}}}return maxLength;}
}

复杂度分析

• 时间复杂度: O(m * n)，其中 m 和 n 是数组长度。
• 空间复杂度: O(m * n)，由于用了二维 DP 表保存状态。

---

解法 2：滚动数组优化动态规划（空间优化）

优化思路

• 注意到在计算 dp[i][j] 时，只需要用到 dp[i-1][j-1] 的值。因此，可以用一维数组代替二维数组，进一步优化空间。
• 滚动更新：从右往左遍历 nums2，避免覆盖之前的状态。

模板代码

class Solution {public int findLength(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;int[] dp = new int[n + 1];int maxLength = 0;// 动态规划填表for (int i = 1; i <= m; i++) {for (int j = n; j >= 1; j--) { // 注意，从右往左遍历 nums2if (nums1[i - 1] == nums2[j - 1]) {dp[j] = dp[j - 1] + 1;maxLength = Math.max(maxLength, dp[j]);} else {dp[j] = 0; // 无法连续时，长度清零}}}return maxLength;}
}

复杂度分析

• 时间复杂度: O(m * n)，遍历数组。
• 空间复杂度: O(n)，使用了一维数组。

---

解法 3：滑动窗口法

核心思想

• 假设固定一个数组 nums1，滑动另一个数组 nums2 进行比较。
• 在滑动的过程中寻找最大公共子数组长度。
  • 如果 nums1 和 nums2 不完全对齐，就逐步滑动 nums2，逐一比较。

模板代码

class Solution {private int maxLen(int[] A, int[] B, int offsetA, int offsetB, int length) {int maxLen = 0, currentLen = 0;for (int i = 0; i < length; i++) {if (A[offsetA + i] == B[offsetB + i]) {currentLen++;maxLen = Math.max(maxLen, currentLen);} else {currentLen = 0;}}return maxLen;}public int findLength(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;int maxLength = 0;// 滑动 nums1 相对于 nums2for (int i = 0; i < m; i++) {int len = Math.min(n, m - i); // 两数组能对齐的长度maxLength = Math.max(maxLength, maxLen(nums1, nums2, i, 0, len));}// 滑动 nums2 相对于 nums1for (int j = 0; j < n; j++) {int len = Math.min(m, n - j); // 两数组能对齐的长度maxLength = Math.max(maxLength, maxLen(nums1, nums2, 0, j, len));}return maxLength;}
}

复杂度分析

• 时间复杂度: O((m + n) * min(m, n))，滑动两遍数组。
• 空间复杂度: O(1)，原地比较，不需要额外空间。

---

解法 4：二分查找 + 哈希

核心思想

• 使用滑动窗口与哈希表结合，通过 二分查找 在所有可能的子数组长度中快速找到最长重复子数组长度。
  1. 利用暴力检查或 Rabin-Karp 哈希验证是否存在长度为 mid 的公共子数组：
     • 用窗口提取长度为 mid 的子数组，进行比对。
  2. 使用二分查找：
     • 如果某个长度是可行的（存在共同子数组），增加长度；
     • 如果不可行，减小长度。

模板代码

import java.util.HashSet;class Solution {public int findLength(int[] nums1, int[] nums2) {int left = 0, right = Math.min(nums1.length, nums2.length);int result = 0;while (left <= right) {int mid = left + (right - left) / 2;if (check(nums1, nums2, mid)) {result = mid;left = mid + 1; // 尝试更长的长度} else {right = mid - 1; // 尝试更短的长度}}return result;}private boolean check(int[] nums1, int[] nums2, int len) {// 使用 HashSet 存储 nums1 长度为 len 的子数组HashSet<String> seen = new HashSet<>();for (int i = 0; i + len <= nums1.length; i++) {seen.add(arrayToString(nums1, i, len));}// 检查 nums2 是否包含相同子数组for (int j = 0; j + len <= nums2.length; j++) {if (seen.contains(arrayToString(nums2, j, len))) {return true;}}return false;}private String arrayToString(int[] nums, int start, int len) {StringBuilder sb = new StringBuilder();for (int i = start; i < start + len; i++) {sb.append(nums[i]).append(",");}return sb.toString();}
}

复杂度分析

• 时间复杂度: O(log(min(m, n)) * (m + n))，二分查找次数乘以每次滑动窗口检查的时间。
• 空间复杂度: O(min(m, n))，为哈希表的空间。

---

变体问题

1. 最长公共子序列 (LCS)：

   • 两数组中非连续元素符合顺序的最长子序列长度。
   • DP 思路与本题类似，但不要求元素连续。

2. 最长公共前缀 (Longest Common Prefix)：

   • 但不局限于以何种顺序，重点是找最大前缀。

3. 编辑距离问题：

   • 在两个字符串之间，进行最少字符操作（包括插入、删除、替换）使其相等。

4. 字符串匹配问题（KMP 或 Rabin Karp）：

   • 查找两个字符串的最大匹配区段。

---

快速 AC 总结

1. 明确问题是连续子数组，直接优先使用滚动 DP 模板。
2. 熟悉时间复杂度要求：若需要 O(m * n) 解决，选择滑动窗口或动态规划。
3. 若需寻求更高效方法，尝试二分和哈希结合的解法。
4. 练习经典变体问题如 LCS，使技术迁移更灵活。