建设银行淮安招聘网站,网站备案安全吗,网站建设考察报告,广告设计与制作专业学什么课程题目 给两个整数数组 nums1 和 nums2 #xff0c;返回 两个数组中 公共的 、长度最长的子数组的长度 。 示例 1#xff1a; 输入#xff1a;nums1 [1,2,3,2,1], nums2 [3,2,1,4,7] 输出#xff1a;3 解释#xff1a;长度最长的公共子数组是 [3,2,1] 。 示例 2#xff1…题目 给两个整数数组 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
解题思路 重复子数组即要求是连续的以nums1 [1,2,3,2,1], nums2 [3,2,1,4,7]为例可以由下表得到最长的子数组的长度为3. 本题的解法很多本文给出动态规划解法。定义dp[i][j]截止数组num1的第i个元素和num2的第j个元素所能包含的最长子数组的最大长度。如果遍历到了num1[i-1]等于num2[j-1]则dp[i][j]可由dp[j-1][j-1]1得到。最后返回dp[i][j]的最大值。 本题值得注意的是使用了dp[i-1][j-1]则i和j都需要从1开始遍历。且设置for循环时需要遍历到nums1.size()即inums1.size()1,是因为需要比较num1和num2到最后一个元素。对应的dp(nums1.size()1, vector(nums2.size()1,0)), 比num1和num2的长度多一个。
代码实现
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {if (nums1.size()0 || nums2.size()0) return 0;vectorvectorint dp(nums1.size()1, vectorint(nums2.size()1,0));int result 0;for (int i1;inums1.size()1;i) {for (int j1;jnums2.size()1;j) {if (nums1[i-1]nums2[j-1]) {dp[i][j]dp[i-1][j-1]1;}result max(result,dp[i][j]);}} return result;}
};
