leetcode代码记录（最长重复子数组

1. 题目：

给两个整数数组 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

2. 我的代码：

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # dp数组下标的含义：i-1：对应的num1索引；j-1：对应的num2索引；dp数组的含义：dp[i][j]范围内的，即nums1[i - 1]、nums2[j - 1]为末尾的数组对应的两个子数组的重复长度
        dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
        
        result = 0

    # 递推公式
        for i in range(1, len(nums1) + 1):
            for j in range(1, len(nums2) + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                result = max(dp[i][j], result)

        return result

这里要用二维dp。

首先，dp数组下标的含义：i-1：对应的num1索引；j-1：对应的num2索引；dp数组的含义：dp[i][j]范围内的，即nums1[i - 1]、nums2[j - 1]为末尾的数组对应的两个子数组的重复长度。

然后，初始化：这里只需要使得第一列和第一行都为0即可，由于真正意义上第一列和第一行应当是nums1[0]和nums2[0]并不一定为0，所以多添加了一列和一行。所以dp的维度总共为：len(nums1) + 1 * len(nums2) + 1

最后，递推公式：在次dp位置对应元素相等时：nums1[i - 1] == nums2[j - 1]，则说明可以从上一个继承过来dp[i][j] = dp[i - 1][j - 1] + 1加一。

顺便统计一下最大值作为返回值即可。