当前位置：首页 > news >正文

实用指南：LeetCode算法日记 - Day 107: 最长重复子数组

news 2026/6/16 13:17:42

1. 最长重复子数组

1.1 题目解析

1.2 解法

1.3 代码实现

1. 最长重复子数组

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

1.1 题目解析

题目本质

找 nums1 和 nums2 中 连续片段（子数组） 的最大公共长度。
关键词：连续、公共子数组、最大长度。
本质可以理解为：“在两个序列中，找一段最长的完全一样的连续区间”。

常规解法

枚举 nums1 中的起点 i
枚举 nums2 中的起点 j
从 i, j 开始往后一个个比，下去统计当前公共连续长度
取所有起点组合中的最大值

// 暴力解法：枚举起点 + 向后比对
public int findLengthBruteForce(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;int ans = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int k = 0;while (i + k < n && j + k < m && nums1[i + k] == nums2[j + k]) {k++;}ans = Math.max(ans, k);}}return ans;
}

问题分析

最坏情况下：
- 外层 i 有 n 个位置
- 中层 j 有 m 个位置
- 内层 k 最坏比较到 O(min(n, m))
复杂度约为 O(n * m * min(n, m))，当 n, m = 1000 时，量级接近 10^9，会超时。
可以预感
- 暴力每次“从头比较”，很多重复比较没有复用。
- 想要更快，就要“记住前面比过的结果”，典型就是 动态规划。

思路转折

观察：如果 nums1[i-1] == nums2[j-1]，那么以这两个位置为结尾的公共子数组长度 = 以前一个位置为结尾的公共子数组长度 + 1。
也就是说，当前结果依赖于“左上方”结果，是标准动态规划形态。
于是我们考虑定义：dp[i][j] = nums1[0..i-1] 和 nums2[0..j-1] 的最长公共后缀长度
则有递推：
- 若 nums1[i-1] == nums2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
- 否则：dp[i][j] = 0（因为必须连续）
这样每个状态只做 O(1) 工作，总状态数 O(n*m)，复杂度刚好能压到 10^6 级别，完全可行。

1.2 解法

算法思想

使用二维动态规划

dp[i][j] 表示以 nums1[i-1]、nums2[j-1] 为结尾的最长公共子数组长度。
递推公式： dp[i][j] = (nums1[i-1] == nums2[j-1]) ? dp[i-1][j-1] + 1 : 0
扫描过程中维护全局最大值 ans。

i）取 n = nums1.length，m = nums2.length。

ii）申请 int[][] dp = new int[n + 1][m + 1];

多一行一列，用作“哨兵行/列”，避免 i-1、j-1 越界。

iii）外层循环 i 从 1 到 n

iv）内层循环 j 从 1 到 m

若 nums1[i-1] == nums2[j-1]：
- dp[i][j] = dp[i-1][j-1] + 1
- 同时用 dp[i][j] 更新 ans。
否则
- dp[i][j] = 0（这里可以省略，因为数组默认 0，但写出来更清晰）。

v）两层循环结束后返回 ans 即为答案。

易错点

下标错位：dp 用的是 1 开始，nums 是 0 开始，内层比较时一定要用 nums1[i-1]、nums2[j-1]。
状态含义搞错：dp[i][j] 是“以 i-1、j-1 为结尾的公共后缀长度”，不是前缀长度，也不是从头开始。
写成最长公共子序列（LCS）思路：LCS 的转移是 max(dp[i-1][j], dp[i][j-1])，会允许不连续，这道题不行，一旦不等就必须断开归零。

1.3 代码实现

class Solution {public int findLength(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;// dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组长度int[][] dp = new int[n + 1][m + 1];int ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > ans) {ans = dp[i][j];  // 维护全局最大值}} else {dp[i][j] = 0; // 写上更直观（其实默认就是 0）}}}return ans;}
}

复杂度分析