【Leetcode刷题Python】718. 最长重复子数组

1 题目

给两个整数数组 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

2 解析

（1）暴力求解 时间复杂度O(n^3)

（2）动态规划 状态：重复子数组的长度 状态转移：从后往前遍历，如果元素相同，则dp等于前一个相同元素的dp加1。 d p [ i ] [ j ] = d p [ i + 1 ] [ j + 1 ] + 1 dp[i][j] = dp[i+1][j+1]+1 dp[i][j]=dp[i+1][j+1]+1

3 Python

（1）方法一：有的例子会超时

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:

        ans = 0
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                k = 0
                while (i+k)