本文主要是介绍【LeetCode】718. 最长重复子数组(中等)——代码随想录算法训练营Day52,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:718. 最长重复子数组
题目描述
给两个整数数组 nums1
和 nums2
,返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1:
输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出:3 解释:长度最长的公共子数组是 [3,2,1] 。
示例 2:
输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出:5
提示:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
文章讲解:代码随想录
视频讲解:动态规划之子序列问题,想清楚DP数组的定义 | LeetCode:718.最长重复子数组_哔哩哔哩_bilibili
题解1:动态规划
思路:使用动态规划法求解子序列问题。
动态规划分析:
- dp 数组以及下标的含义:dp[i][j] 代表以 num1[i - 1] 和 nums2[j - 1] 结尾的最长公共子数组长度。
- 递推公式:num1[i - 1] 等于 nums2[j - 1] 时,dp[i][j] = dp[i - 1][j - 1] + 1。
- dp 数组初始化:全部初始化为0。
- 遍历顺序:从前到后。
- 打印 dp 数组:以输入 nums1 = [1,2,3,2,1]、nums2 = [3,2,1,4,7] 为例,dp 数组为 [ [ 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0 ], [ 0, 0, 1, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0 ], [ 0, 0, 2, 0, 0, 0 ], [ 0, 0, 0, 3, 0, 0 ] ]。
/*** @param {number[]} nums1* @param {number[]} nums2* @return {number}*/
var findLength = function(nums1, nums2) {let res = 0;const dp = new Array(nums1.length + 1).fill().map(() => new Array(nums2.length + 1).fill(0));for (let i = 1; i <= nums1.length; i++) {for (let j = 1; j <= nums2.length; j++) {if (nums1[i - 1] === nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;if (dp[i][j] > res) {res = dp[i][j];}}}}return res;
};
分析:时间复杂度为 O(n * m),空间复杂度为 O(n * m)。
收获
练习使用动态规划法求解子序列问题,子数组是连续的子序列,遇到2个数组的公共子序列问题时,dp 数组需要有2个维度。
这篇关于【LeetCode】718. 最长重复子数组(中等)——代码随想录算法训练营Day52的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!