718. 最长重复子数组

题目

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

 

示例：

输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。 链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

提示：

1 <= len(A), len(B) <= 10000 <= A[i], B[i] < 100

---

1、暴力解法：

public int findLength(int[] A, int[] B) { // 1. 暴力解法 (超出时间限制) int result = 0; for (int i = 0; i < A.length; i++) { for (int j = 0; j < B.length; j++) { int k = 0; while (i + k < A.length && j + k < B.length && B[j + k] == A[i + k]) { k = k + 1; } result = Math.max(result, k); } } return result; }

---

2. 动态规划：

 

借用 Python 表示数组的方法，

A[i:] 表示数组 A 中 索引 i 到数组末尾的范围 对应的子数组。

 

如果 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]。

public int findLength(int[] A, int[] B) { int lenA = A.length; int lenB = B.length; int[][] dpArr = new int[lenA + 1][lenB + 1]; int result = 0; // 从尾部开始往前比较 for (int i = lenA - 1; i >= 0; i--) { for (int j = lenB - 1; j >= 0; j--) { if (A[i] == B[j]) { // dpArr[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀 dpArr[i][j] = dpArr[i + 1][j + 1] + 1; } else { dpArr[i][j] = 0; } result = Math.max(result, dpArr[i][j]); } } return result; }