echo

任生命穿梭 时间的角落

0%

最长重复子数组

Posted on In Valine:

718. 最长重复子数组

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

示例 1:

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

说明:

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

我们可以想到暴力解法，即枚举数组 A 的起始位置 i 与数组 B 中的起始位置 j，然后计算A[i: ] 和 B[j: ]的最长公共前缀 k。保存 k 的最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findLength(int[] A, int[] B) {
        int m = A.length, n = B.length;
        int ans = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int k = 0;
                while(k + i < m && k + j < n && A[i + k] == B[j + k]){
                    k++;
                }
                ans = Math.max(k, ans);
            }
        }
        return ans;
    }
}

时间复杂度O(n^3)，空间复杂度O(1)。

方法一：动态规划

在暴力法中我们做了很多重复比较，设 A 数组为[1, 2, 3]，B 数组为[1, 2, 4]，在暴力法中A[2] 与 B[2] 被比较了三次，分别是计算 A[0: ] 与 B[0: ]的最长前缀和、A[1: ] 与 B[1: ]的最长前缀和、A[2: ] 与 B[2: ]的最长前缀和时产生的。

我们可以优化这个过程，使任意 A[i] 与 B[j] 都只被比较一次。对于A[i: ] 和 B[j: ] 的最长前缀和，如果A[i] == B[j] 那么 A[i: ] 和 B[j: ] 的最长前缀和 = A[i+1: ] 和 B[j+1: ] 的最长前缀和 + 1，否则A[i: ] 和 B[j: ] 的最长前缀和为 0 。

动态规划解法如下：

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

时间复杂度O(mn)，空间复杂度O(mn)，m 和 n 分别为数组 A 和数组 B 的长度。

方法二：滑动窗口

我们注意到两个位置之所以会比较多次，使因为重复子数组在两个数组中的位置可能不同：

1
2
A = [3, 6, 1, 2, 4]
B = [7, 1, 2, 9]

重复子数组[1, 2] 位置没有对齐，我们人为地将它们对齐，然后只需进行一次遍历即可得到最长重复子数组的长度。

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

我们可以枚举 A 和 B 所有的对齐方式：

  1. A 不变，B 的首元素与 A 中的某一个元素对齐；
  2. 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
class Solution {
    public int findLength(int[] A, int[] B) {
        int m = A.length, n = B.length;
        int ans = 0;
        //B 不变
        for(int i = 0; i < m; i++){
            //计算剩下元素的最大长度
            int len = Math.min(n, m - i);
            ans = Math.max(maxLength(A, B, i, 0, len), ans);
        }
		//A 不变
        for(int i = 0; i < n; i++){
            int len = Math.min(m, n - i);
            ans = Math.max(maxLength(A, B, 0, i, len), ans);
        }
        return ans;
    }
	//从对齐位置开始比较
    public int maxLength(int[] A, int[] B, int addA, int addB, int len){
        int ans = 0, k = 0;
        for(int i = 0; i < len; i++){
            if(A[addA + i] == B[addB + i]){
                ++k;
            }else{
                k = 0;
            }
            ans = Math.max(ans, k);
        }
        return ans;
    }
}

时间复杂度O((m + n) * min(m, n))，空间复杂度O(1)。