一、题目描述
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
二、示例
三、思路讲解
由题目分析，我们可以先看最后两个数组的最后一个数，如果相同的话，再看前一个 如果符合的话 加上自身相同的1，所以最后的结果和之前的子结果是相关的。就可以写出dp方程，dp[i][j] = dp[i-1][j-1]+1,开始时先对数组进行一个初始化。为了优化我们可以将二维数组换成一维数组，方程就变为
四 、代码
const findLength = (A, B) => {
const m
= A.length
;
const n
= B.length
;
const dp
= new Array(m
+ 1);
for (let i
= 0; i
<= m
; i
++) {
dp
[i
] = new Array(n
+ 1).fill(0);
}
let res
= 0;
for (let i
= 1; i
<= m
; i
++) {
for (let j
= 1; j
<= n
; j
++) {
if (A[i
- 1] == B[j
- 1]) {
dp
[i
][j
] = dp
[i
- 1][j
- 1] + 1;
}
res
= Math
.max(dp
[i
][j
], res
);
}
}
return res
;
}
const findLength = (A, B) => {
const n
= A.length
;
const m
= B.length
;
var max
= 0;
const dp
= new Array(m
+ 1).fill(0);
for (let i
= 0; i
< n
; i
++) {
for (let j
= m
; j
> 0; j
--) {
dp
[j
] = A[i
] == B[j
- 1] ? dp
[j
- 1] + 1 : 0;
if (dp
[j
] > max
) max
= dp
[j
];
}
}
return max
;
}
五、结果
