718最长重复子数组

最长重复子数组

Tags Companies 给两个整数数组 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 <= 1000
• 0 <= nums1[i], nums2[i] <= 100

题解:

class Solution {
public:
//dp[i][j]表示以i-1结束的nums1和j-1结束的nums2的最长重复子数组长度
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector(nums2.size()+1,0));
        int ans=0; 
        for (int i = 1; i <=nums1.size(); i++) //这里从1开始存储
        {
            for (int j= 1; j <= nums2.size(); j++)
            {
                //只是dp的存储后移了一位,nums的存储并没有后移,所以nums的对比要-1
                if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1; //因为要根据i-1更新所以前面集体后移
                if(ans<dp[i][j]) ans=dp[i][j];
            }
        }
        return ans;
    }
};