题目(难度:中等):
给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:长度最长的公共子数组是 [3, 2, 1]
上面逻辑实现后会发现:
var findLength = function (A, B) {
let _result = 0
if (!A.length || !B.length) return _result
for (let i = 0; i < A.length; i++) {
let index = i,
middle = 0,
j = 0
while (j < B.length) {
if (A[index] === B[j]) {
middle++
index++
_result = Math.max(_result, middle)
} else {
// i重置,则会使A之后的元素只能计算到首次与B相同的连续长度;
index = i
// i不重置,则B中当前j之后的数据可能与index之前的数据匹配长度才最长(及j之后的数据第一个与A相同的索引在index之前)
// index = i
middle = 0
}
j++
}
}
return _result
}
当 B 中有多个数据与 A 中相同,即一个 A 的起点,可以再 B 中出现多个 A[i]=B[j],此时 i 是向后继续迭代还是重置
惊不惊喜,意不意外,上来就是一个错误的解法
皮归皮,上面的思路有问题的是:
声明个中间变量记录,如果相同+1,不然重置为 0如果不同继续向后查找相同的元素
那重新换下这部分思路尝试下:
/**
* @param {number[]} A
* @param {number[]} B
* @return {number}
*/
var findLength = function (A, B) {
let n = A.length,
m = B.length,
_result = 0
if (!n || !m) return _result
for (let i = 0; i < n; i++) {
let end = Math.min(m, n - i)
// i
let maxlen = maxLength(A, B, i, 0, end)
_result = Math.max(_result, maxlen)
}
for (let j = 0; j < m; j++) {
let end = Math.min(n, m - j)
let maxlen = maxLength(A, B, 0, j, end)
_result = Math.max(_result, maxlen)
}
function maxLength(A, B, a, b, len) {
let num = 0,
middle = 0
for (let i = 0; i < len; i++) {
if (A[a + i] == B[b + i]) {
middle++
num = Math.max(num, middle)
} else {
middle = 0
}
}
return num
}
return _result
}
/**
* @param {number[]} A
* @param {number[]} B
* @return {number}
*/
var findLength = function (A, B) {
let n = A.length,
m = B.length,
_result = 0,
map = new Map()
if (!n || !m) return _result
for (let i = 0; i < n; i++) {
for (let j = m - 1; j >= 0; j--) {
let prev = map.get(j) || 0
if (A[i] === B[j]) {
map.set(j + 1, prev + 1)
} else {
map.set(j + 1, 0)
}
_result = Math.max(_result, map.get(j + 1))
}
}
return _result
}
/**
* @param {number[]} A
* @param {number[]} B
* @return {number}
*/
var findLength = function (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 ans = 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
}
ans = Math.max(dp[i][j], ans)
}
}
return ans
}