0718. 最长重复子数组

0718. 最长重复子数组 #

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

题目大意 #

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

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

说明

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

示例

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

解题思路 #

思路 1:暴力(超时) #

  1. 枚举数组 $nums1$ 和 $nums2$ 的子数组开始位置 $i$、$j$。
  2. 如果遇到相同项,即 $nums1[i] == nums2[j]$,则以 $nums1[i]$、$nums2[j]$ 为前缀,同时向后遍历,计算当前的公共子数组长度 $subLen$ 最长为多少。
  3. 直到遇到超出数组范围或者 $nums1[i + subLen] == nums2[j + subLen]$ 情况时,停止遍历,并更新答案。
  4. 继续执行 $1 \sim 3$ 步,直到遍历完,输出答案。

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        size1, size2 = len(nums1), len(nums2)
        ans = 0
        for i in range(size1):
            for j in range(size2):
                if nums1[i] == nums2[j]:
                    subLen = 1
                    while i + subLen < size1 and j + subLen < size2 and nums1[i + subLen] == nums2[j + subLen]:
                        subLen += 1
                    ans = max(ans, subLen)
        
        return ans

思路 1:复杂度分析 #

  • 时间复杂度:$O(n \times m \times min(n, m))$。其中 $n$ 是数组 $nums1$ 的长度,$m$ 是数组 $nums2$ 的长度。
  • 空间复杂度:$O(1)$。

思路 2:滑动窗口 #

暴力方法中,因为子数组在两个数组中的位置不同,所以会导致子数组之间会进行多次比较。

我们可以将两个数组分别看做是两把直尺。然后将数组 $nums1$ 固定, 让 $nums2$ 的尾部与 $nums1$ 的头部对齐,如下所示。

1
2
nums1 =             [1, 2, 3, 2, 1]
nums2 = [3, 2, 1, 4, 7]

然后逐渐向右移动直尺 $nums2$,比较 $nums1$ 与 $nums2$ 重叠部分中的公共子数组的长度,直到直尺 $nums2$ 的头部移动到 $nums1$ 的尾部。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
nums1 =             [1, 2, 3, 2, 1]
nums2 =    [3, 2, 1, 4, 7]

nums1 =             [1, 2, 3, 2, 1]
nums2 =       [3, 2, 1, 4, 7]

nums1 =             [1, 2, 3, 2, 1]
nums2 =          [3, 2, 1, 4, 7]

nums1 =             [1, 2, 3, 2, 1]
nums2 =             [3, 2, 1, 4, 7]

nums1 =             [1, 2, 3, 2, 1]
nums2 =                [3, 2, 1, 4, 7]

nums1 =             [1, 2, 3, 2, 1]
nums2 =                   [3, 2, 1, 4, 7]

nums1 =             [1, 2, 3, 2, 1]
nums2 =                      [3, 2, 1, 4, 7]

nums1 =             [1, 2, 3, 2, 1]
nums2 =                         [3, 2, 1, 4, 7]

在这个过程中求得的 $nums1$ 与 $nums2$ 重叠部分中的最大的公共子数组的长度就是 $nums1$ 与 $nums2$ 数组中公共的、长度最长的子数组长度。

思路 2:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def findMaxLength(self, nums1, nums2, i, j):
        size1, size2 = len(nums1), len(nums2)
        max_len = 0
        cur_len = 0
        while i < size1 and j < size2:
            if nums1[i] == nums2[j]:
                cur_len += 1
                max_len = max(max_len, cur_len)
            else:
                cur_len = 0
            i += 1
            j += 1
        return max_len

    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        size1, size2 = len(nums1), len(nums2)
        res = 0
        for i in range(size1):
            res = max(res, self.findMaxLength(nums1, nums2, i, 0))

        for i in range(size2):
            res = max(res, self.findMaxLength(nums1, nums2, 0, i))
        
        return res

思路 2:复杂度分析 #

  • 时间复杂度:$O(n + m) \times min(n, m)$。其中 $n$ 是数组 $nums1$ 的长度,$m$ 是数组 $nums2$ 的长度。
  • 空间复杂度:$O(1)$。

思路 3:动态规划 #

1. 划分阶段 #

按照子数组结尾位置进行阶段划分。

2. 定义状态 #

定义状态 $dp[i][j]$ 为:「以 $nums1$ 中前 $i$ 个元素为子数组($nums1[0]…nums2[i - 1]$)」和「以 $nums2$ 中前 $j$ 个元素为子数组($nums2[0]…nums2[j - 1]$)」的最长公共子数组长度。

3. 状态转移方程 #
  1. 如果 $nums1[i - 1] = nums2[j - 1]$,则当前元素可以构成公共子数组,此时 $dp[i][j] = dp[i - 1][j - 1] + 1$。
  2. 如果 $nums1[i - 1] \ne nums2[j - 1]$,则当前元素不能构成公共子数组,此时 $dp[i][j] = 0$。
4. 初始条件 #
  • 当 $i = 0$ 时,$nums1[0]…nums1[i - 1]$ 表示的是空数组,空数组与 $nums2[0]…nums2[j - 1]$ 的最长公共子序列长度为 $0$,即 $dp[0][j] = 0$。
  • 当 $j = 0$ 时,$nums2[0]…nums2[j - 1]$ 表示的是空数组,空数组与 $nums1[0]…nums1[i - 1]$ 的最长公共子序列长度为 $0$,即 $dp[i][0] = 0$。
5. 最终结果 #
  • 根据状态定义, $dp[i][j]$ 为:「以 $nums1$ 中前 $i$ 个元素为子数组($nums1[0]…nums2[i - 1]$)」和「以 $nums2$ 中前 $j$ 个元素为子数组($nums2[0]…nums2[j - 1]$)」的最长公共子数组长度。在遍历过程中,我们可以使用 $res$ 记录下所有 $dp[i][j]$ 中最大值即为答案。

思路 3:代码 #

 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

思路 3:复杂度分析 #

  • 时间复杂度:$O(n \times m)$。其中 $n$ 是数组 $nums1$ 的长度,$m$ 是数组 $nums2$ 的长度。
  • 空间复杂度:$O(n \times m)$。
本站总访问量  次  |  您是本站第  位访问者