LeetCode 「中等」718.最长重复子数组
题目描述
给两个整数数组 nums1 和 nums2 ，返回两个数组中公共的、长度最长的子数组的长度 。
示例
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
解答
暴力法
Code
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findLength = function(nums1, nums2) {
const len1 = nums1.length;
const len2 = nums2.length;
let maxlen = 0;
for (let i = 0; i < len1; ++i) {
for (let j = 0; j < len2; ++j) {
if (nums2[j] === nums1[i]) {
let sublen = 1; // 公共序列长度至少为 1
while (
i + sublen < len1 &&
j + sublen < len2 &&
nums1[i + sublen] === nums2[j + sublen]
) {
++sublen; // 公共子序列长度每次增加 1，考察新的一项
}
maxlen = Math.max(maxlen, sublen);
}
}
}
return maxlen;
};
动态规划
思路
- 定义状态
- 使用一个二维数组
dp，其中dp[i][j]表示nums1的前i和元素和nums2的前j个元素中，以nums1[i - 1]和nums2[j - 1]结尾的最长公共子数组的长度
- 状态转移
- 如果
nums1[i - 1]等于nums2[j - 1]，则dp[i][j] = dp[i - 1][j - 1] + 1 - 如果
nums1[i - 1]不等于nums2[j - 1]，则dp[i][j] = 0
- 初始化
dp[0][j] = 0，因为nums1的前 0 个元素和nums2的前j个元素没有公共子数组dp[i][0] = 0，因为nums1的前i个元素和nums2的前 0 个元素没有公共子数组
- 计算结果
- 遍历
dp数组，找到其中的最大值，即为两个数组中公共的、长度最长的子数组的长度
Code
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findLength = function(nums1, nums2) {
const m = nums1.length;
const n = nums2.length;
// 定义一个数组 dp，大小为 (m + 1) * (n + 1)，其中 m 和 n 分别是 nums1 和 nums2 的长度
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
let maxlen = 0;
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (nums1[i - 1] === nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = 0;
}
maxlen = Math.max(maxlen, dp[i][j]);
}
}
return maxlen;
}
降维优化
dp[i][j] 只依赖上一行上一列的对角线的值，所以我们从右上角开始计算。也就是沿着从右到左、从上到下的顺序遍历 dp 数组
Code
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findLength = function(nums1, nums2) {
const m = nums1.length;
const n = nums2.length;
const dp = new Array(n + 1).fill(0);
let maxlen = 0;
for (let i = 1; i <= m; ++i) {
for (let j = n; j >= 1; --j) {
if (nums1[i - 1] === nums2[j - 1]) {
dp[j] = dp[j - 1] + 1;
} else {
dp[j] = 0;
}
maxlen = Math.max(maxlen, dp[j]);
}
}
return maxlen;
}