718. 最长重复子数组
难度中等
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。
提示： （1）1 <= len(A), len(B) <= 1000 （2）0 <= A[i], B[i] < 100
思路1.0：
（1）设较长数组为A，较短数组为B，dp[n]即为B的前n位中，长度最长的公共子数组长度。
（2）利用B中的滑动数组来判断公共子数组，滑动数组可分为两种情况讨论：
1）尚未形成长度>=2的公共子数组，找到A中所有与B[right]相等的元素，并保存偏移量
2）已形成长度>=2的公共子数组，从1）中保存的偏移量下手，查看后面的元素是否符合，从而形成较长的公共子数组。
（3）dp[n]=max(dp[n-1],arr[left:right+1]是否在A中存在)
代码1.0：
class Solution {
public:
int findLength(vector
<int>& A
, vector
<int>& B
) {
int lenA
= A
.size(), lenB
= B
.size();
if (lenA
< lenB
) {
vector
<int> temp
;
temp
= A
;
A
= B
;
B
= temp
;
}
lenB
= B
.size();
vector
<int> dp(lenB
+1);
dp
[0] = 0;
int right
= 0, left
= 0;
int offset
= 0;
while (right
< lenB
)
{
if (left
== right
)
{
B
[right
]
}
}
}
};
第1）步的处理中，预感到如果测试数据中，较长数组里有大量的重复元素，那我这执行时间肯定会爆炸，
而且我的方法里也没有用到动态规划。。。自己看到子数组就想把滑动数组强行拥上去。去题解看看有没有更好的方法吧。
思路2.0（已看题解）：
dp[n][n]表示数组A以A[n]为结尾，数组B以B[n]为结尾的俩数组，能提供的最长公共长度。
代码2.0（已完成）
class Solution {
public:
int findLength(vector
<int>& A
, vector
<int>& B
) {
int lenA
= A
.size(), lenB
= B
.size();
vector
<vector
<int>> dp(lenA
+1, vector
<int>(lenB
+1, 0));
dp
[0][0] = 0;
int rst
= 0;
for (int i
= 1; i
<= lenA
; ++i
)
{
for (int j
= 1; j
<= lenB
; ++j
)
{
if (A
[i
- 1] != B
[j
- 1]) dp
[i
][j
] = 0;
if (A
[i
- 1] == B
[j
- 1]) dp
[i
][j
] = dp
[i
- 1][j
- 1] + 1;
rst
= max(rst
, dp
[i
][j
]);
}
}
return rst
;
}
};
