0718. 最长重复子数组 #

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

题目大意 #

描述：给定两个整数数组 nums1、nums2。

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

说明：

$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：动态规划 #

定义状态 dp[i][j] 表示为：以下标 i - 1 结尾的 nums1 和以下标 j - 1 结尾的 nums2 的最长重复子数组长度。
两重遍历 nums1、nums2，计算 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。
最后用 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：复杂度分析 #

时间复杂度：
空间复杂度：