718-Maximum length of repeated subarry

题目描述

链接：https://leetcode.com/problems/maximum-length-of-repeated-subarray/description/

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

解释： 给定两个数组nums1和 nums2, 求两个数组的最长公共子数组

案例：
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].

解释：最长公共子数组为[3,2,1]

基本思想

经典二维动态规划。\(dp[i][j]\) 表示以nums[i]和 nums[j]为结尾的 \(nums1[0...,i-1]\)和 \(nums2[0...,j-1]\) 的最长公共子串，则

• 如果 \(nums1[i] == nums2[j]\),\(dp[i][j]\) = \(dp[i-1][j-1]\)+1
• 反之，\(dp[i][j]\) = 0

时间复杂度\(o(n^2)\)

代码

c++

    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        if (n<=0 || m<=0) return 0;
        vector<vector<int>> dp(n, vector<int>(m,0));
        int res = 0;
        // - 初始化
        for(int i=0; i<m;++i) {
            if (nums1[0] == nums2[i])
              dp[0][i] = 1;
            res = max(dp[0][i], res);
        }
        for(int i=0; i<n;++i) {
            if (nums1[i] == nums2[0]) 
              dp[i][0] = 1;
            res = max(dp[i][0], res);
        }
        for(int i=1;i<n;++i) {
            for(int j=1;j<m;++j) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i-1][j-1]+1;
                } 
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};

python

def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        n,m = len(nums1), len(nums2)
        if n<=0 or m<0: return 0
        dp = [[0] * m for i in range(n)]
        res = 0
        for i in range(n):
            for j in range(m):
                if (nums1[i] == nums2[j]):
                    if (i-1)>=0 and (j-1)>=0:
                        dp[i][j] = dp[i-1][j-1]+1
                    else:
                        dp[i][j] = 1 
                res = max(res, dp[i][j])
        return res