目录
力扣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 <= 10000 <= nums1[i], nums2[i] <= 100
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
}
};解析代码
子数组是数组中连续的⼀段，习惯上以某一个位置为结尾来研究。由于是两个数组， 因此可以尝试：以第一个数组的 i 位置为结尾以及第二个数组的 j 位置为结尾来解决问题。
状态表示：
结合题目得到：dp[i][j] 表示以第一个数组的 i 位置为结尾，以及第二个数组的 j 位置为结尾公共的 、长度最长的子数组的长度。
状态转移方程：
对于 dp[i][j] ，当 nums1[i] == nums2[j] 的时候，此时最长重复子数组的长度应该等于 1 加上除去最后一个位置时，以 i - 1, j - 1 为结尾的最长重复子数组的长度。 因此，状态转移方程为： dp[i][j] = 1 + dp[i - 1][j - 1]，nums1[i] != nums2[j] 时 为 0，所以可以初始化dp表为0。
初始化：
为了处理越界的情况，可以添加一行和一列， dp 数组的下标从 1 开始，这样就无需初始化。 第一行表示第⼀个数组为空，此时没有重复子数组，因此里面的值设置成 0 即可， 第一列也是同理。
填表顺序：从上往下填写每一行，每一行从左往右。
最后返回dp表的最大值。
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size(), ret = 0;
vector<vector<int>> dp(m + 1,vector<int>(n + 1, 0));
//dp[i][j] 表示以第一个数组的 i 位置为结尾，
// 以及第二个数组的 j 位置为结尾公共的 、长度最长的子数组的长度。
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
if(nums1[i - 1] == nums2[j - 1]) // 注意原数组下标映射
{
dp[i][j] = dp[i - 1][j - 1] + 1;
ret = max(ret, dp[i][j]);
}
}
}
return ret;
}
};