题干
给两个整数数组 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
想法
动态规划 dp[i][j]表示到AB从ij位置到末尾的最长前缀。 从后往前遍历 dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0; 注意边界即可
Java代码
package daily
;
public class FindLength {
public int findLength(int[] A
, int[] B
) {
int lenA
= A
.length
, lenB
= B
.length
;
int res
= 0;
int[][] dp
= new int[lenA
+ 1][lenB
+ 1];
for (int i
= lenA
- 1; i
>= 0; i
--) {
for (int j
= lenB
- 1; j
>= 0; j
--) {
if (A
[i
] == B
[j
]) {
dp
[i
][j
] = dp
[i
+ 1][j
+ 1] + 1;
} else {
dp
[i
][j
] = 0;
}
res
= Math
.max(res
, dp
[i
][j
]);
}
}
return res
;
}
public static void main(String
[] args
) {
FindLength findLength
= new FindLength();
int[] A
= {1, 2, 3, 2, 1};
int[] B
= {3, 2, 1, 4, 7};
System
.out
.println(findLength
.findLength(A
, B
));
}
}
我的leetcode代码都已经上传到我的githttps://github.com/ragezor/leetcode
