给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 1:
输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。说明:
1 <= len(A), len(B) <= 10000 <= 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; } }