您是小站的第 27953 位访客,欢迎~

您现在的位置是: 网站首页 > 程序设计  > leetcode 

leetcode-0718. 最长重复子数组

2021年9月26日 00:19 120人围观

简介给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

    718. 最长重复子数组

    给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

    示例:

     
    输入: 
    A: [1,2,3,2,1] 
    B: [3,2,1,4,7] 
    输出:3 
    解释: 
    长度最长的公共子数组是 [3, 2, 1] 。 
    

    提示:

    • 1 <= len(A), len(B) <= 1000
    • 0 <= A[i], B[i] < 100

    这是一道求长度,不需要具体值的题,所以考虑用动态规划。题目涉及到两个字符串,一维数组没法表示,需要二维数组,所以这是二维动态规划问题

    动态规划的关键在状态方程,在这里我们定义dp[i][j]用来表示以i结尾的nums1和以j结尾的nums2的子数组的长度,那么则有

    class Solution { 
    public: 
        int findLength(vector<int>& nums1, vector<int>& nums2) { 
            if (nums1.size() * nums2.size() == 0) { 
                return 0; 
            } 
    
            vector<vector<int>> dp(nums1.size(), vector<int>(nums2.size(), 0)); 
            // dp[i][j]表示以nums1[i]、nums2[j]结尾的最长子数组长度 
    
            int max_len = 0; 
            for (int i = 0; i < nums1.size(); i++) { 
                for (int j = 0; j < nums2.size(); j++) { 
                    if (nums1[i] == nums2[j]) { 
                        if (i * j == 0) { 
                            dp[i][j] = 1; 
                        } 
                        else { 
                            dp[i][j] = dp[i-1][j-1] + 1; 
                        } 
                        if (dp[i][j] > max_len) { 
                            max_len = dp[i][j]; 
                        } 
                    } 
                } 
            } 
            return max_len; 
        } 
    };