718. 最长重复子数组

发表于 分类于 阅读次数： Waline： 本文字数： 896 阅读时长 ≈ 3 分钟

考点

  • LCS

思路

一、问题概述

给定两个整数数组 \[ \text{nums}_1 = [a_1, a_2, \dots, a_{n_1}], \quad \text{nums}_2 = [b_1, b_2, \dots, b_{n_2}] \] 要求找出 同时出现在两个数组中的最长连续子数组 的长度。

注意关键词是 连续（subarray），而不是子序列（subsequence）。

二、动态规划建模思想

2.1 与 LCS 的本质区别

  • 最长公共子序列（LCS）：允许跳过元素
  • 最长重复子数组：必须连续，一旦断开，长度直接归零

因此，本题的 DP 状态 不允许继承横向或纵向的最大值，只能从 左上角对角线 转移。

三、状态定义（State Definition）

定义二维 DP 数组： \[ f[i][j] \] 表示：

以 \[ \text{nums}_1[i-1] \quad \text{和} \quad \text{nums}_2[j-1] \] 作为结尾元素的最长公共连续子数组长度

换言之，f[i][j] 描述的是： “必须以这两个位置结尾”的最长长度。

四、初始值设计（Initialization）

4.1 边界状态

当任意一个数组长度为 0 时，不存在公共子数组： \[ f[0][j] = 0,\quad f[i][0] = 0 \]

4.2 实现方式说明

在代码中通过：

1
memset(f, 0, sizeof(f));

直接将整个 DP 数组初始化为 0，从而隐式完成所有边界条件。

五、状态转移方程（Transition）

5.1 元素不相等

若： \[ \text{nums}_1[i-1] \ne \text{nums}_2[j-1] \] 则连续性被破坏： \[ f[i][j] = 0 \]

5.2 元素相等（核心转移）

若： \[ \text{nums}_1[i-1] = \text{nums}_2[j-1] \] 则可以在前一个连续匹配的基础上延长： \[ \boxed{ f[i][j] = f[i-1][j-1] + 1 } \] 这是本题 唯一有效的状态转移路径。

六、答案的获取方式（Answer）

最长重复子数组 不一定以数组末尾结束，因此答案为： \[ \text{ans} = \max_{1 \le i \le n_1,\; 1 \le j \le n_2} f[i][j] \] 实现中需在 DP 过程中维护一个全局最大值。

七、二维 DP 完整逻辑总结

  • 初始化所有状态为 0
  • 双重循环枚举 (i, j)
  • 仅在元素相等时进行对角线转移
  • 实时更新全局最大值

时间复杂度： \[ O(n_1 \times n_2) \] 空间复杂度： \[ O(n_1 \times n_2) \]

八、滚动数组优化（空间压缩）

8.1 优化依据

状态转移只依赖： \[ f[i][j] \leftarrow f[i-1][j-1] \] 因此可以将二维数组压缩为一维。

8.2 一维状态定义

令： \[ f[j] = \text{当前处理到 } i \text{ 时的 } f[i][j] \]

8.3 反向遍历的必要性

为保证 f[j-1] 仍表示上一行的 f[i-1][j-1]， j 必须 从大到小遍历。

8.4 一维状态转移

\[ f[j] = \begin{cases} f[j-1] + 1, & \text{nums}_1[i-1] = \text{nums}_2[j-1] \\ 0, & \text{otherwise} \end{cases} \]

九、复杂度对比

实现方式 时间复杂度 空间复杂度
二维 DP \(O(n_1 n_2)\) \(O(n_1 n_2)\)
滚动数组 \(O(n_1 n_2)\) \(O(n_2)\)

十、AC代码

10.1 二维 DP 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    static const int maxn = 1e3 + 5;
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int f[maxn][maxn];
        memset(f, 0, sizeof(f));
        int n1 = nums1.size(), n2 = nums2.size(), res = 0;
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (nums1[i - 1] != nums2[j - 1])
                    continue;
                f[i][j] = 1 + f[i - 1][j - 1];
                res = max(res, f[i][j]);
            }
        }
        return res;
    }
};

10.2 滚动数组（一维 DP）版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    static const int maxn = 1e3 + 5;
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int f[maxn];
        memset(f, 0, sizeof(f));
        int n1 = nums1.size(), n2 = nums2.size(), res = 0;
        for (int i = 1; i <= n1; ++i) {
            for (int j = n2; j >= 1; --j) {
                if (nums1[i - 1] != nums2[j - 1])
                    f[j] = 0;
                else {
                    f[j] = 1 + f[j - 1];
                    res = max(res, f[j]);
                }
            }
        }
        return res;
    }
};