[718. 最长重复子数组]
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 1:
输入:
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
思路：动态规划
dp[i] [j] 表示以i, j 为结尾的连续公共子数组
那么：
dp[i][j] = A[i] == B[j] ? dp[i+1][j+1]+1 : 0;
public int findLength(int[] A, int[] B) {
int maxLen = 0;
int[][] dp = new int[A.length+1][B.length+1];
for (int i = A.length-1; i >= 0; i--) {
for (int j = B.length-1; j >= 0; j--) {
dp[i][j] = A[i] == B[j] ? dp[i+1][j+1]+1 : 0;
maxLen = Math.max(maxLen, dp[i][j]);
}
}
return maxLen;
}
思路二 ：滑动窗口
分别将AB数组按不同的偏移量对齐即可
public int findLength(int[] A, int[] B) {
int maxLen = 0;
//A数组向前移
for (int i = 0; i < A.length-1; i++) {
//分别表示AB的指针和他们前一位的最大公共子数组长度
int ai = i, bi = 0, last = 0;
while (ai < A.length && bi < B.length){
last = A[ai++] == B[bi++] ? last+1: 0;
maxLen = Math.max(maxLen, last );
}
}
//B数组向前移
for (int i = 0; i < B.length-1; i++) {
//分别表示AB的指针和他们前一位的最大公共子数组长度
int ai = 0, bi = i, last = 0;
while (ai < A.length && bi < B.length){
last = A[ai++] == B[bi++] ? last+1: 0;
maxLen = Math.max(maxLen, last );
}
}
return maxLen;
}
思路三 ：二分+hash
如果数组 A 和 B 有一个长度为 k 的公共子数组，那么它们一定有长度为 j <= k 的公共子数组。这样我们可以通过二分查找的方法找到最大的 k。
而为了优化时间复杂度，在二分查找的每一步中，我们可以考虑使用哈希的方法来判断数组 A 和 B 中是否存在相同特定长度的子数组。
注意到序列内元素值小于 100100100 ，我们使用 Rabin-Karp 算法来对序列进行哈希。具体地，我们制定一个素数 base，那么序列 S 的哈希值为：
形象地说，就是把 S 看成一个类似 base 进制的数（左侧为高位，右侧为低位），它的十进制值就是这个它的哈希值。由于这个值一般会非常大，因此会将它对另一个素数 mod 取模。
当我们要在一个序列 S 中算出所有长度为 len 的子序列的哈希值时，我们可以用类似滑动窗口的方法，在线性时间内得到这些子序列的哈希值。例如，如果我们当前得到了 S[0:len] 的哈希值，希望算出 S[1:len+1] 的哈希值时，有下面这个公式：
即删去最高位 S[0]，其余位自动进一，并补上最低位 S[len+1]。
在二分查找的每一步中，我们使用哈希表分别存储这两个数组的所有长度为 len 的子数组的哈希值，将它们的哈希值进行比对，如果两序列存在相同的哈希值，则认为两序列存在相同的子数组。为了防止哈希碰撞，我们也可以在发现两个子数组的哈希值相等时，进一步校验它们本身是否确实相同，以确保正确性。但该方法在本题中很难发生哈希碰撞，因此略去进一步校验的部分。
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;
}
}