718. 最长重复子数组

原题链接：

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;}
}

方法二：滑动窗口

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;}
}

方法三：二分查找 + 哈希

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;}
}