暴力
解题思路
需要先两层 for 循环确定两个数组起始位置；
然后再来一个循环，来从两个起始位置开始比较，取得重复子数组的长度；
以 nums1 = [1, 2, 3, 2, 1]，nums2 = [3, 2, 1, 4, 7] 为例：最大长度为 3；
nums2[0] => 3 nums2[1] => 2 nums2[2] => 1 nums2[3] => 4 nums2[4] => 7 nums1[0] => 1 0 0 1 0 0 nums1[1] => 2 0 1 0 0 0 nums1[2] => 3 10 0 0 0 nums1[3] => 2 0 10 0 0 nums1[4] => 1 0 0 10 0
复杂度
-
时间复杂度：
O(n^3)； -
空间复杂度：
O(1)；
代码实现
const findLength = (A, B) => {
const m = A.length;
const n = B.length;
let res = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
// 遇到相同项
if (A[i] == B[j]) {
let subLen = 1; // 公共子序列长度至少为 1
while (i + subLen < m && j + subLen < n && A[i + subLen] == B[j + subLen]) { // 新的一项也相同
subLen++; // 公共子序列长度每次增加 1，考察新的一项
}
res = Math.max(subLen, res);
}
}
}
return res;
};
动态规划
解题思路
确定 dp 数组以及下标的含义：以下标 i - 1 为结尾的 A，和以下标 j - 1 为结尾的 B，最长重复子数组长度为 dp[i][j]；
- 如果要定义成 以下标 i - 1 为结尾的 A，和以下标 j - 1 为结尾的 B，最长重复子数组长度为 dp[i][j]； 也可以；
- 需要在初始化的时候判断 nums1[i] == nums2[0]、nums1[0] == nums2[j] 是否相等；
- 这里选择第一种方式；
确定递推公式：当 A[i - 1] === B[j - 1] 的时候，dp[i][j] = dp[i - 1][j - 1] + 1；
如何初始化 dp 数组：
- 第一种：根据 dp[i][j] 的定义，dp[i][0] 和 dp[0][j] 其实都是没有意义的！但 dp[i][0] 和 dp[0][j] 要初始化为 0，是为了方便递归公式的递推；
- 第二种：如果定义 dp[i][j] 为以下标 i 为结尾的 A，和以下标 j 为结尾的 B，那么 第一行和第一列毕竟要进行初始化；
// 如果 nums1[i] 与 nums2[0] 相同的话，对应的 dp[i][0]就要初始为 1，因为此时最长重复子数组为 1 for (int i = 0; i < nums1.size(); i++) if (nums1[i] == nums2[0]) dp[i][0] = 1; // nums2[j] 与 nums1[0] 相同的话，同理 for (int j = 0; j < nums2.size(); j++) if (nums1[0] == nums2[j]) dp[0][j] = 1;确定遍历顺序：先遍历 A、B 都可以，这里外层遍历 A，内层遍历 B；
举例推导 dp 数组：以 nums1 = [1, 2, 3, 2, 1]，nums2 = [3, 2, 1, 4, 7] 为例：最大长度为 3；
j = 0 j = 1 j = 2 j = 3 j = 4 j = 5 dp[0][j] 0 0 0 0 0 0 dp[1][j] 0 0 0 1 0 0 dp[2][j] 0 0 1 0 0 0 dp[3][j] 0 10 0 0 0 dp[4][j] 0 0 20 0 0 dp[5][j] 0 0 0 30 0
复杂度
-
时间复杂度：
O(n * m)； -
空间复杂度：
O(n * m)，空间压缩后为O(n)；
代码实现
JavaScript
JavaScript
const findLength = (A, B) => {
let res = 0;
const m = A.length;
const n = B.length;
const dp = new Array(m + 1).fill(0).map(it => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
// 遇到 A[i - 1] === B[j - 1]，则更新 dp 数组
if (A[i - 1] === B[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
res = Math.max(res, dp[i][j]);
}
}
return res;
};
// 空间压缩
const findLength = (A, B) => {
let res = 0;
const m = A.length;
const n = B.length;
let dp = new Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
for (let j = n; j > 0; j--) {
if (nums1[i - 1] === nums2[j - 1]) {
dp[j] = dp[j - 1] + 1;
} else {
dp[j] = 0;
}
res = Math.max(res, dp[j]);
}
}
return res;
}
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 674. 最长连续递增序列
上一篇
评论
