LeetCode718-最长重复子数组

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--) { // 注意，从右往左遍历 nums2 if (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 相对于 nums2 for (int i = 0; i < m; i++) { int len = Math.min(n, m - i); // 两数组能对齐的长度 maxLength = Math.max(maxLength, maxLen(nums1, nums2, i, 0, len)); } // 滑动 nums2 相对于 nums1 for (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：二分查找 + 哈希 核心思想 使用滑动窗口与哈希表结合，通过 二分查找 在所有可能的子数组长度中快速找到最长重复子数组长度。 利用暴力检查或 Rabin-Karp 哈希验证是否存在长度为 mid 的公共子数组： 用窗口提取长度为 mid 的子数组，进行比对。 使用二分查找： 如果某个长度是可行的（存在共同子数组），增加长度；如果不可行，减小长度。 模板代码 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))，为哈希表的空间。

---

变体问题

最长公共子序列 (LCS)：

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

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

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

编辑距离问题：

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

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

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

---

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