718.最长重复子数组

发表于： 分类于：
字数： 677 阅读：≈ 2分钟

😄718.最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

思路

基本思想

拿一个数组中的元素去与另外一个数组中的元素进行匹配，一旦遇到了相同的元素，后面的元素依次匹配，直到遇到第一个不匹配的元素，就这样一直统计，返回统计出现的最大值，就是公共最长子数组的长度

根据上面的流程分析，可以判断得到当前元素的最长公共子数组与前面的元素有关，所以我们可以利用动态规划来做，当前元素一旦相等，当前元素的对应的dp数组就有可能更新，并且更新与前一个元素有关

所以设置一个二维dp数组，dp[i][j]代表以第i个元素和第j个元素结尾的两个数组，最长公共子数组的长度是多大

形成的递推方程为： $$ dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1) $$ 取max是因为防止[0,1,3,2,1]和[0,1,3]中更新1出现的问题，其实1对应的dp应该是2，但是最后的1也会进行匹配，不加max会导致1对应的dp数组变成1

执行流程

  1. 初始化二维dp数组，使其全为0，这样匹配时初次匹配的两个元素对应的dp会变成1
  2. 按照递推方程更新dp数组
  3. 更新dp数组的过程中，统计出现的最大值
  4. 返回最大值作为最终的结果

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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 res = 0;
        for(int i=0;i<nums1.size();++i){
            for(int j=0;j<nums2.size();++j){
                if(nums1[i]==nums2[j]){//遇到匹配的元素就可能更新dp数组
                    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
                }
                //当前元素对应的dp数组中的元素应该+1，因为下标0对应第一个元素
                if(res<dp[i+1][j+1])  
                    res=dp[i+1][j+1];
            }
        }
        return res;
    }
};

总结

与300题类似，遇到相等的元素就可能更新，所以设置对应的递推方程

拿第一个数组中的元素依次与第二个数组中的每一个元素进行比较，公共的长度与前面的元素有关