leetcode *718. 最长重复子数组（2020.7.1）

【题目】*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

【解题思路1】动态规划

以[1, 2, 3, 2, 1]和[3,2,1,4]为例 比较A[i] 、B[j]，如果不相等，则公共子序列肯定不包括它们俩；如果相等，则它们两至少可以组成长度为1的子数组，然后继续考虑它们前面的序列即 A[0]-A[i-1] 和 B[0]-B[j-1] 这两个区间【能为它们提供多大的公共长度】 比较A[i-1] 、B[j-1]，如果不相等，则公共子序列肯定不包括它们俩；如果相等，则继续考虑它们再前面的序列【能为它们俩提供多大的公共长度】…… 这就转化为子问题了

dp[i][j] 定义： 长度为 i 以 A[i-1] 为末尾的序列，和长度为 j以 B[j-1] 为末尾的序列，二者的最大公共后缀序列长度（该公共序列以A[i-1]（B[j-1]）为末尾项） 边界条件：i0 || j0 ，即其中一个长度为0，是空子数组，没有公共长度，dp[i][j] = 0 转移方程：若A[i-1] == B[j-1]，则dp[i][j] = dp[i - 1][j - 1] + 1，否则dp[i][j] = 0，最后答案即为所有 dp[i][j] 中的最大值 注：从前往后即dp[0][0]往dp[lenA-1][lenB-1]计算，和从后往前，是一样的

class Solution { public int findLength(int[] A, int[] B) { int max = 0; int lenA = A.length, lenB = B.length; int[][] dp = new int[lenA + 1][lenB + 1]; for (int i = 1; i <= lenA; i++) { for (int j = 1; j <= lenB; j++) { if (A[i - 1] == B[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = 0; max = Math.max(max, dp[i][j]); } } return max; } }

【解题思路2】滑动窗口

以[1, 2, 3, 2, 1]和[3,2,1,4]为例

class Solution { public int findLength(int[] A, int[] B) { int aLength = A.length, bLength = B.length; //total是总共运行的次数 int total = aLength + bLength - 1; int max = 0; for (int i = 0; i < total; i++) { //判断数组A和数组B比较的起始位置和比较的长度 int aStart = 0; int bStart = 0; int len = 0; if (i < aLength) { aStart = aLength - i - 1; bStart = 0; len = i + 1; } else { aStart = 0; bStart = i - aLength+1; len = Math.min(bLength - bStart, aLength); } int maxlen = maxLength(A, B, aStart, bStart, len); max = Math.max(max, maxlen); } return max; } //计算A和B在上面图中红色框内的最大长度 public int maxLength(int[] A, int[] B, int aStart, int bStart, int len) { int max = 0, count = 0; for (int i = 0; i < len; i++) { if (A[aStart + i] == B[bStart + i]) { count++; max = Math.max(max, count); } else { count = 0; } } return max; } }

分开写，感觉会好理解一点区间到底是怎么取的

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