1. 题目描述
2. 题目解析
- 首先最先想到的应该是暴力，也就是直接跑3层循环，暴力解出ans的最大值
- 其次，此题是一个动态规划，我们来看一张图：
相当于我们求的是斜着的这一部分最多可以连续多长，此时动规的公式就比较明显了，
array[i][j] = array[i-1][j-1] + 1; - 最后是一种解法：滑动窗口，顾名思义，也就是通过保持A不变，滑动B，保持B不变，滑动A，最后取出其中最大的ans；
3. 题目代码
1. 动规
public static int findLength1(int[] A, int[] B) {
int ans = 0;
int[][] array = new int[A.length + 1][B.length + 1];
for (int i = 1; i <= A.length; i++) {
for (int j = 1; j <= B.length; j++) {
if (A[i - 1] == B[j - 1]) {
array[i][j] = array[i - 1][j - 1] + 1;
ans = Math.max(ans, array[i][j]);
} else {
array[i][j] = 0;
}
}
}
return ans;
}2. 滑动窗口代码
public static int findLength(int[] A, int[] B) {
int ans = 0;
for (int i = 0; i < A.length; i++) {
int k = 0;
int len1 = i;
int len2 = 0;
while (len1 < A.length && len2 < B.length) {
if (A[len1] == B[len2]) {
k++;
len1++;
len2++;
ans = Math.max(ans, k);
} else {
k = 0;
len1++;
len2++;
}
}
}
for (int i = 0; i < B.length; i++) {
int k = 0;
int len1 = 0;
int len2 = i;
while (len1 < A.length && len2 < B.length) {
if (A[len1] == B[len2]) {
k++;
len1++;
len2++;
ans = Math.max(ans, k);
} else {
k = 0;
len1++;
len2++;
}
}
}
return ans;
}