718、最长的重复数组
给两个整数数组 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$
链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray
题解
1、暴力
class Solution {
public int findLength(int[] A, int[] B) {
int max = 0;
for (int i = 0;i < A.length;i++) {
for (int j = 0;j < B.length;j++) {
if (A[i] == B[j]) {
int count = 1;
for (int k = 1; k < Math.min(A.length - i,B.length - j);k++) {
if (A[i + k] == B[j + k]) {
count++;
} else {
break;
}
}
max = Math.max(count,max);
}
}
}
return max;
}
}
2、动态规划
dp[i][j] 表示A[i:] 和 B[j:]最长公共前缀
class solution {
public int findLength(int[] A,int[] B) {
int n = A.length, m = B.length;
int[][] dp = new int[n + 1][m + 1];
int max = 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;
max = Math.max(max,dp[i][j]);
}
}
return max;
}
}
3、滑动窗口
class Solution {
public int findLength(int[] A, int[] B) {
int n = A.length, m = B.length;
int ret = 0;
for (int i = 0; i < n; i++) {
int len = Math.min(m, n - i);
int maxlen = maxLength(A, B, i, 0, len);
ret = Math.max(ret, maxlen);
}
for (int i = 0; i < m; i++) {
int len = Math.min(n, m - i);
int maxlen = maxLength(A, B, 0, i, len);
ret = Math.max(ret, maxlen);
}
return ret;
}
public int maxLength(int[] A, int[] B, int addA, int addB, int len) {
int ret = 0, k = 0;
for (int i = 0; i < len; i++) {
if (A[addA + i] == B[addB + i]) {
k++;
} else {
k = 0;
}
ret = Math.max(ret, k);
}
return ret;
}
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/
4、二分查找 + 哈希
class Solution {
int mod = 1000000009;
int base = 113;
public int findLength(int[] A, int[] B) {
int left = 1, right = Math.min(A.length, B.length) + 1;
while (left < right) {
int mid = (left + right) >> 1;
if (check(A, B, mid)) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
public boolean check(int[] A, int[] B, int len) {
long hashA = 0;
for (int i = 0; i < len; i++) {
hashA = (hashA * base + A[i]) % mod;
}
Set<Long> bucketA = new HashSet<Long>();
bucketA.add(hashA);
long mult = qPow(base, len - 1);
for (int i = len; i < A.length; i++) {
hashA = ((hashA - A[i - len] * mult % mod + mod) % mod * base + A[i]) % mod;
bucketA.add(hashA);
}
long hashB = 0;
for (int i = 0; i < len; i++) {
hashB = (hashB * base + B[i]) % mod;
}
if (bucketA.contains(hashB)) {
return true;
}
for (int i = len; i < B.length; i++) {
hashB = ((hashB - B[i - len] * mult % mod + mod) % mod * base + B[i]) % mod;
if (bucketA.contains(hashB)) {
return true;
}
}
return false;
}
// 使用快速幂计算 x^n % mod 的值
public long qPow(long x, long n) {
long ret = 1;
while (n != 0) {
if ((n & 1) != 0) {
ret = ret * x % mod;
}
x = x * x % mod;
n >>= 1;
}
return ret;
}
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
