407，动态规划和滑动窗口解决最长重复子数组
Never be afraid to reach for the stars, because even if you fall, you'll always be wearing a parent-chute.
永远不要害怕去摘星星，因为就算你跌下来，你永远有“父母牌”降落伞防身。
问题描述
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
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
动态规划
这题一看就知道其实就是求最长公共子串问题，不懂的可以看下前面的，只不过换了种说法，换汤不换药，本质还是没变。我们就以题中的示例画个图来看一下
最长的公共子数组就是上面红色所对应的[3,2,1]，长度是3。
递推公式是
if(s1.charAt(i) == s2.charAr(j))dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = 0;
有了递推公式，代码就容易多了，我们来看下完整代码
1public int findLength(int[] A, int[] B) {
2 int max = 0;
3 int[][] dp = new int[A.length + 1][B.length + 1];
4 for (int i = 1; i <= A.length; i++) {
5 for (int j = 1; j <= B.length; j++) {
6 if (A[i - 1] == B[j - 1]) {
7 dp[i][j] = dp[i - 1][j - 1] + 1;
8 max = Math.max(max, dp[i][j]);
9 }
10 }
11 }
12 return max;
13}
14
这里的二维数组dp长和宽都要加1是为了减少判断，当然也可以不加1，但这样会多了一些边界的判断，我们来看下不加1的代码
1public int findLength(int[] A, int[] B) {
2 int max = 0;
3 int[][] dp = new int[A.length][B.length];
4 for (int i = 0; i < A.length; i++) {
5 for (int j = 0; j < B.length; j++) {
6 if (A[i] == B[j]) {
7 if (i > 0 && j > 0)
8 dp[i][j] = dp[i - 1][j - 1] + 1;
9 else
10 dp[i][j] = 1;
11 max = Math.max(max, dp[i][j]);
12 }
13 }
14 }
15 return max;
16}
如果看过之前写的，我们还可以把二维数组改为一维数组来减少空间复杂度
1public int findLength(int[] A, int[] B) {
2 int max = 0;
3 int[] dp = new int[B.length + 1];
4 for (int i = 1; i <= A.length; i++) {
5 for (int j = B.length; j >= 1; j--) {
6 if (A[i - 1] == B[j - 1])
7 dp[j] = dp[j - 1] + 1;
8 else
9 dp[j] = 0;
10 max = Math.max(max, dp[j]);
11 }
12 }
13 return max;
14}
注意这里第二个for循环是从后往前遍历的，这是因为dp后面的值会依赖前面的值，但前面的值不会依赖后面的值，如果我们改变后面的值对前面的值不会有影响，但改变前面的值会影响面的值，所以这里我们从后往前计算是最合适的。
滑动窗口
第2种方式是滑动窗口，文字叙述不好理解，我们就以[1, 2, 3, 2, 1]和[3,2,1,4]为例来举例说明，这两个数组我故意弄成两个长度不一样的，我们画个图来看一下
相当于说第一个数组位置不动，第二个数组每次往右移一位，搞懂了上的分析过程，代码就容易多了，我们来看下
1public int findLength(int[] A, int[] B) {
2 if (A.length < B.length)
3 return findLengthHelper(A, B);
4 return findLengthHelper(B, A);
5}
6
7public int findLengthHelper(int[] A, int[] B) {
8 int aLength = A.length, bLength = B.length;
9 //total是总共运行的次数
10 int total = aLength + bLength - 1;
11 int max = 0;
12 for (int i = 0; i < total; i++) {
13 //下面一大坨主要判断数组A和数组B比较的起始位置和比较的长度
14 int aStart = 0;
15 int bStart = 0;
16 int len = 0;
17 if (i < aLength) {
18 aStart = aLength - i - 1;
19 bStart = 0;
20 len = i + 1;
21 } else {
22 aStart = 0;
23 bStart = i - aLength + 1;
24 len = Math.min(bLength - bStart, aLength);
25 }
26 int maxlen = maxLength(A, B, aStart, bStart, len);
27 max = Math.max(max, maxlen);
28 }
29 return max;
30}
31
32//计算A和B在上面图中红色框内的最大长度
33public int maxLength(int[] A, int[] B, int aStart, int bStart, int len) {
34 int max = 0, count = 0;
35 for (int i = 0; i < len; i++) {
36 if (A[aStart + i] == B[bStart + i]) {
37 count++;
38 max = Math.max(max, count);
39 } else {
40 count = 0;
41 }
42 }
43 return max;
44}
总结
其实这道题求的就是最长公共子串问题，通过上面的图分析，可以发现第一种方式和第二种方式都比较好理解，但第一种方式代码明显比第二种少了很多。
●
●
●
●
长按上图，识别图中二维码之后即可关注。
如果喜欢这篇文章就点个"赞"吧