跳至主要內容

0718. 最长重复子数组

ITCharge大约 4 分钟

0718. 最长重复子数组open in new window

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

题目链接

题目大意

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

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

说明

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

示例

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

解题思路

思路 1:暴力(超时)

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

思路 1:代码

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×m×min(n,m))O(n \times m \times min(n, m))。其中 nn 是数组 nums1nums1 的长度,mm 是数组 nums2nums2 的长度。
  • 空间复杂度O(1)O(1)

思路 2:滑动窗口

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

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

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

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

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]

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

思路 2:代码

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)×min(n,m)O(n + m) \times min(n, m)。其中 nn 是数组 nums1nums1 的长度,mm 是数组 nums2nums2 的长度。
  • 空间复杂度O(1)O(1)

思路 3:动态规划

1. 划分阶段

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

2. 定义状态

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

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

思路 3:代码

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×m)O(n \times m)。其中 nn 是数组 nums1nums1 的长度,mm 是数组 nums2nums2 的长度。
  • 空间复杂度O(n×m)O(n \times m)