本文最后更新于594 天前,其中的信息可能已经过时,如有错误请发送邮件到tomding1065@gmail.com
视频讲解:https://www.bilibili.com/video/BV178411H7hV
https://programmercarl.com/0718.%E6%9C%80%E9%95%BF%E9%87%8D%E5%A4%8D%E5%AD%90%E6%95%B0%E7%BB%84.html
1.本题最重要的是对于dp数组的定义的问题,本题按照卡哥所讲的方法定义的`dp[i][j]表示nums1里的i – 1之前的数和nums2 j – 1之前的数重复子数组的长度(dp[i][j] :以下标i – 1为结尾的A,和以下标j – 1为结尾的B,最长重复子数组长度为dp[i][j]。 (特别注意: “以下标i – 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 ))。
这里节选代码随想录(如果定义 dp[i][j]为 以下标i为结尾的A,和以下标j 为结尾的B,那么 第一行和第一列毕竟要进行初始化,如果nums1[i] 与 nums2[0] 相同的话,对应的 dp[i][0]就要初始为1, 因为此时最长重复子数组为1。 nums2[j] 与 nums1[0]相同的话,同理。)基于此本题就没有什么难度。
CPP
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
int res = 0;
for(int i = 1; i <= nums1.size(); i++){
for(int j = 1; j <= nums2.size(); j++){
if(nums1[i - 1] == nums2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;
res = max(dp[i][j], res);
}
}
return res;
}
};