0718. 最长重复子数组 #

标签：数组、二分查找、动态规划、滑动窗口、哈希函数、滚动哈希
难度：中等

题目大意 #

给定两个整数数组 nums1、nums2。要求：计算两个数组中公共的、长度最长的子数组长度。

解题思路 #

动态规划求解。

定义状态 dp[i][j] 表示为：以下标 i - 1 结尾的 nums1 和以下标 j - 1 结尾的 nums2 的最长重复子数组长度。

两重遍历 nums1、nums2，计算 dp[i][j]。

如果 nums1[i] == nums2[j]，则当前元素可以构成公共子数组，则 dp[i][j] = dp[i - 1][j - 1] + 1。
如果 nums1[i] != nums2[j]，则当前元素不能构成公共子数组，则 dp[i][j] = 0。

最后用 res 记录下最大的 dp[i][j] 即为答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        size1 = len(nums1)
        size2 = len(nums2)
        dp = [[0 for _ in range(size2 + 1)] for _ in range(size1 + 1)]
        res = 0
        for i in range(1, size1 + 1):
            for j in range(1, size2 + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] > res:
                    res = dp[i][j]

        return res