leetcode-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

提示:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

方法1:动态规划

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        len1 = len(nums1)
        len2 = len(nums2)
        dp = [[0 for j in range(0, len2+1)]for i in range(0, len1+1)]
        res = 0
        for i in range(1, len1+1):
            for j in range(1, len2+1):
                if nums1[i-1]==nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                    res = max(res, dp[i][j])
                else:
                    dp[i][j] = 0
        return res