原题链接：
718. 最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
完成情况：
题解：
方法一：动态规划
package 西湖算法题解___中等题;
public class __718最长重复子数组__动态规划 {
//子数组的话，默认是连续的。
public int findLength(int[] nums1, int[] nums2) {
/*
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
当然了，肯定是要求顺序，而非连续。
那么必然就需要用到动态数组，采取累积的形式
*/
int n = nums1.length,m = nums2.length;
int dp_findLength [][] = new int[n+1][m+1];
int res = 0;
for (int i=n-1;i>=0;i--){
for (int j=m-1;j>=0;j--){
dp_findLength[i][j] = (nums1[i] == nums2[j] ? dp_findLength[i+1][j+1] + 1:0);
res = Math.max(res,dp_findLength[i][j]);
}
}
return res;
}
}
方法二：滑动窗口
文章来源：https://www.toymoban.com/news/detail-680611.html
package 西湖算法题解___中等题;
public class __718最长重复子数组__滑动窗口 {
public int findLength(int[] nums1, int[] nums2) {
int n = nums1.length,m = nums2.length;
int res = 0;
for (int i=0;i<n;i++){
int len = Math.min(m,n-i);
int maxLen = maxLength(nums1,nums2,i,0,len);
res = Math.max(res,maxLen);
}
for (int i=0;i<m;i++){
int len = Math.min(n,m-i);
int maxLen = maxLength(nums1,nums2,0,i,len);
res = Math.max(res,maxLen);
}
return res;
}
private int maxLength(int[] nums1, int[] nums2, int addA, int addB, int len) {
int res = 0,k=0;
for (int i=0;i<len;i++){
if (nums1[addA+i] == nums2[addB+i]){
k++;
}else {
k=0;
}
res = Math.max(res,k);
}
return res;
}
}
方法三：二分查找 + 哈希
文章来源地址https://www.toymoban.com/news/detail-680611.html
package 西湖算法题解___中等题;
import java.util.HashSet;
import java.util.Set;
public class __718最长重复子数组__二分查找_哈希表 {
int mod = 1000000009;
int base = 113;
public int findLength(int[] nums1, int[] nums2) {
int left = 1,right = Math.min(nums1.length,nums2.length)+1;
while (left < right){
int mid = (left + right) >> 1;
if (myCheck(nums1,nums2,mid)){
left = mid +1;
}else {
right = mid;
}
}
return left - 1;
}
private boolean myCheck(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 的值
* @param x
* @param n
* @return
*/
private long qPow(long x, long n) {
long res = 1L;
while (n != 0){
if ((n&1) != 0){
res = res * x % mod;
}
x = x*x % mod;
n >>= 1;
}
return res;
}
}
到了这里，关于718. 最长重复子数组的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
