0718. 最长重复子数组

0718. 最长重复子数组 #

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

题目大意 #

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

解题思路 #

动态规划求解。

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

两重遍历 nums1nums2,计算 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
本站总访问量  次  |  您是本站第  位访问者