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