代码随想录 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

解题思路
重复子数组即要求是连续的，以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()（即i<nums1.size()+1）,是因为需要比较num1和num2到最后一个元素。对应的dp(nums1.size()+1, vector(nums2.size()+1,0)), 比num1和num2的长度多一个。

代码实现

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size()==0 || nums2.size()==0) return 0;
        vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1,0));
        int result = 0;
        for (int i=1;i<nums1.size()+1;i++) {
            for (int j=1;j<nums2.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;
    }
};