leetcode刷题笔记-718. 最长重复子数组
题目
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
1
2
3
4
5
6
7
8
| 示例 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
2
| 1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
|
子数组其实就是连续的子序列。
思路1
说明
依旧是用动态规划的思路，dp数组肯定需要一个二维的了，之前写过最长递增子序列，当时用的dp数组下标的含义是以j下标为结尾的最长递增子序列的长度。本题也是一样的思路
dp[i][j]代表数组1中以i结尾，数组2中以j结尾的最长公共子数组的长度（包括i和j）；
根据这个定义，可以推算出递推公式，当 nums1[i] == nums2[j] 的时候，说明子数组可以被扩张，此时dp[i][j] = dp[i-1][j-1] +1，含义是当前的最长公共子数组的长度是前一位的最长公共子数组的长度加一（加上当前位）
1
2
3
| if(nums1[i] == nums2[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
|
我们需要对这个dp数组进行初始化，需要初始化第一列和第一行，代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| for (int i = 0; i < nums1.size(); i++) {
if (nums1[i] == nums2[0]) {
dp[i][0] = 1;
}
}
for (int j = 0; j < nums2.size(); j++) {
if (nums2[j] == nums1[0]) {
dp[0][j] = 1;
}
}
|
完整代码
随后就是i和j都从1开始遍历了，更新出一个最大值返回就可以了。完整代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size(), vector<int>(nums2.size(), 0));
bool contains = false;
for (int i = 0; i < nums1.size(); i++) {
if (nums1[i] == nums2[0]) {
dp[i][0] = 1;
contains = true;
}
}
for (int j = 0; j < nums2.size(); j++) {
if (nums2[j] == nums1[0]) {
dp[0][j] = 1;
contains = true;
}
}
int result =
contains
? 1
: 0;
for (int i = 1; i < nums1.size(); i++) {
for (int j = 1; j < nums2.size(); j++) {
if (nums1[i] == nums2[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if (dp[i][j] > result) {
result = dp[i][j];
}
}
}
return result;
}
};
|
时间复杂度和空间复杂度都是O(N^2)；
思路2
说明
上文的思路中，dp数组下标的含义是以i和j结尾的最长公共子序列的长度。我们可以将其改成dp[i][j]代表以i-1和j-1结尾的最长重复子数组的长度。
这样做就可以不对数组提前进行初始化了，因为dp[0][x] 和dp[x][0]都是没有意义的。
基本思路都是一致的，只不过递推方程的判断改为判断nums1[i-1] == nums2[j-1]了，另外dp数组的长度也需要加一。
完整代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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 result = 0;
for (int i = 1; i < dp.size(); i++) {
for (int j = 1; j < dp[0].size(); j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if (dp[i][j] > result) {
result = dp[i][j];
}
}
}
return result;
}
};
|
压缩为一维数组
这道题中的dp递推方程每次都只和[i-1][j-1]有关系，所以可以将二维数组直接压缩为一维，倒叙遍历j就可以沿用上一层dp的结果了，代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<int> dp(nums2.size() + 1, 0);
int result = 0;
for (int i = 1; i <= nums1.size(); i++) {
for (int j = nums2.size(); j >= 1; j--) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[j] = dp[j - 1] + 1;
} else {
dp[j] = 0;
}
if (dp[j] > result) {
result = dp[j];
}
}
}
return result;
}
};
|
类似题目
1143. 最长公共子序列
这道题要求是最长的公共子序列，就不是让你算子数组了。虽然题目给出的是字符串，但本质上我们可以把它当作数组来处理，没有区别。
完整的代码如下，采用的是思路2，具体参考注释中的说明。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int longestCommonSubsequence(string a, string b) {
int result = 0;
vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));
for (int i = 1; i <= a.size(); i++) {
for (int j = 1; j <= b.size(); j++) {
if (a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
if (dp[i][j] > result) {
result = dp[i][j];
}
}
}
return result;
}
};
|
爱发电
