最长重复子数组
Pin Young Lv9

题目描述

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

示例:

输入:
A: [1, 2, 3, 2, 1]
B: [3, 2, 1, 4, 7]
输出:3
解释:长度最长的公共子数组是 [3, 2, 1] 。

提示:

  • 1 <= len(A), len(B) <= 1000
  • 0 <= A[i], B[i] < 100

暴力方法

最简单的方法,暴力方法,我们知道最长公共子数组长度最大值为数组A和B中长度较小值。我们先固定最长值为min(len(A), len(B)),然后遍历A和B,判断此长度是否有公共子数组,找到,则返回此值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int findLength(int[] A, int[] B) {
int len = Math.min(A.length, B.length);
int res_len = len;
while (res_len > 0) {
for (int ai = 0; ai + res_len <= len; ai++) {
for (int bi = 0; bi + res_len <= len; bi++) {
// 判断固定长度的子数组是否相等
if (subArrayIsSame(A, B, ai, bi, res_len)) {
return res_len;
}
}
}
// 如果不相等,最大长度减一
res_len--;
}
return res_len;
}

public boolean subArrayIsSame(int[] A, int[] B, int ai, int bi, int len) {
for (int i = 0; i < len; i++) {
if (A[ai + i] != B[bi + i]) {
return false;
}
}
return true;
}

复杂度分析

  • 时间复杂度:Ο(N³),因为要遍历A、B和公共子数组。
  • 空间复杂度:Ο(1)。

滑动窗口

以题目为例,它们的最长重复子数组是 [3, 2, 1],在 A 与 B 中的开始位置不同。但如果我们知道了开始位置,我们就可以根据它们将 A 和 B 进行「对齐」,即:

1
2
3
A = [1, 2, 3, 2, 1]
B = [3, 2, 1, 4, 7]
↑ ↑ ↑

此时,最长重复子数组在 A 和 B 中的开始位置相同,我们就可以对这两个数组进行一次遍历,得到子数组的长度。我们可以枚举 A 和 B 所有的对齐方式。对齐的方式有两类:第一类为 A 不变,B 的首元素与 A 中的某个元素对齐;第二类为 B 不变,A 的首元素与 B 中的某个元素对齐。对于每一种对齐方式,我们计算它们相对位置相同的重复子数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int findLength(int[] A, int[] B) {
int lenA = A.length;
int lenB = B.length;
int ret = 0;
for (int i = 0; i < lenA; i++) {
int len = Math.min(lenA - i, lenB);
int maxLen = maxLength(A, B, i, 0, len);
ret = Math.max(ret, maxLen);
}

for (int i = 0; i < lenB; i++) {
int len = Math.min(lenB - i, lenA);
int maxLen = maxLength(A, B, 0, i, len);
ret = Math.max(ret, maxLen);
}
return ret;
}

// 对齐后计算最长公共子数组
public int maxLength(int[] A, int[] B, int indexA, int indexB, int len) {
int ret = 0;
int maxLen = 0;
for (int i = 0; i < len; i++) {
if (A[indexA + i] == B[indexB + i]) {
maxLen++;
} else {
maxLen = 0;
}
ret = Math.max(ret, maxLen);
}
return ret;
}

复杂度分析

  • 时间复杂度: Ο((M + N) × min(M, N))。
  • 空间复杂度: Ο(1)。

    M 表示数组 A 的长度,N 表示数组 B 的长度。

动态规划

我们使用A[i],B[j]分别表示两个数组对应下标的值。如果 A[i] == B[j],那么我们知道 A[i:] 与 B[j:] 的最长公共前缀为 A[i + 1:] 与 B[j + 1:] 的最长公共前缀的长度加一,否则我们知道 A[i:] 与 B[j:] 的最长公共前缀为零。这样我们就可以提出动态规划的解法:令 dp[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀,那么答案即为所有 dp[i][j] 中的最大值。如果 A[i] == B[j],那么 dp[i][j] = dp[i + 1][j + 1] + 1,否则 dp[i][j] = 0。
考虑到这里 dp[i][j] 的值从 dp[i + 1][j + 1] 转移得到,所以我们需要倒过来,首先计算 dp[len(A) - 1][len(B) - 1],最后计算 dp[0][0]。

1
2
3
4
5
6
7
8
9
10
11
12
public int findLength(int[] A, int[] B) {
int n = A.length, m = B.length;
int[][] dp = new int[n + 1][m + 1];
int ret = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
ret = Math.max(ret, dp[i][j]);
}
}
return ret;
}

复杂度分析

  • 时间复杂度: O(M × N)。
  • 空间复杂度: O(M × N)。

    N 表示数组 A 的长度,M 表示数组 B 的长度。

来源

最长重复子数组 | 力扣(LeetCode)
最长重复子数组 | 题解(LeetCode)


文章标题:最长重复子数组
文章作者:cylong
文章链接:https://0skyu.cn/posts/96c1.html
有问题或者建议欢迎在下方评论。欢迎转载、引用,但希望标明出处,感激不尽(●’◡’●)