718. 最长重复子数组

Difficulty
Medium
Tags
动态规划
URL
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
Star
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 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 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100
通过次数123,174提交次数217,070

法 1 动态规划 —— 双序列型

思路
与
🕢
1143. 最长公共子序列 区别在于本题的子串是连续的。所以状态转移方程如下：
if nums1[i] == nums2[j]:
		dp[i][j] = dp[i-1][j-1]+1
else:
		dp[i][j] = 0
题解
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        nums1 = [-1] + nums1
        nums2 = [-1] + nums2

        dp = [[0] * len(nums2) for _ in nums1]
        res = 0
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if nums1[i] == nums2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = 0
            
                res = max(res, dp[i][j])

        return res
如果要还原出来具体的公共子串，见如下代码：
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        nums1 = [-1] + nums1
        nums2 = [-1] + nums2

        dp = [[0] * len(nums2) for _ in nums1]
        max_length = 0 # 最长公共子串的长度
        rdx = None # 记下最长公共子串在 nums1 中的位置
        
        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if nums1[i] == nums2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
            
                    if dp[i][j] > max_length:
                        max_length = dp[i][j]
                        idx = i

        # 最长公共子串
        res = nums1[idx+1-max_length:idx+1]
        
        return max_length

法 2 滑动窗口

思路
有点像卷积，想象两把尺子，错开之后比较相同的部分，找最长相同的串就好了。
notion imagenotion image

法 3 字符串匹配算法

用二分法来试探长度，然后用滚动哈希来求解