0718. 最长重复子数组

0718. 最长重复子数组 #

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

题目大意 #

描述:给定两个整数数组 nums1nums2

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

说明

  • $1 \le nums1.length, nums2.length \le 1000$。
  • $0 \le nums1[i], nums2[i] \le 100$。

示例

1
2
3
4
5
6
7
输入nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出3
解释长度最长的公共子数组是 [3,2,1] 


输入nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出5

解题思路 #

思路 1:动态规划 #

  1. 定义状态 dp[i][j] 表示为:以下标 i - 1 结尾的 nums1 和以下标 j - 1 结尾的 nums2 的最长重复子数组长度。
  2. 两重遍历 nums1nums2,计算 dp[i][j]
    1. 如果 nums1[i] == nums2[j],则当前元素可以构成公共子数组,则 dp[i][j] = dp[i - 1][j - 1] + 1
    2. 如果 nums1[i] != nums2[j],则当前元素不能构成公共子数组,则 dp[i][j] = 0
  3. 最后用 res 记录下最大的 dp[i][j] 即为答案。

思路 1:代码 #

 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

思路 1:复杂度分析 #

  • 时间复杂度
  • 空间复杂度
本站总访问量  次  |  您是本站第  位访问者