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