LeetCode 718 Maximum Length of Repeated Subarray

LeetCode

<div>

Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.

Example 1:

<pre>Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3,2,1]. </pre>

Example 2:

<pre>Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] Output: 5 </pre>

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

</div>

题目大意：

两数组的最长相等子数组

解题思路：

由于是两数组匹配，所以是匹配性DP
dp[i][j]为以nums1[i-1], nums2[j-1]为结尾的最长重复数组，答案为滚动最大值

dp[i][j] = dp[i-1][j-1] + 1 if nums1[i-1] == nums2[j-1]
         = 0                if nums1[i-1] != nums2[j-1]

类似题目： LeetCode 1143 Longest Common Subsequence, 求最长公共子字符串 Karat 002 Longest Common Continuous Subarray 一样的题目，结果类型不同：最长长度和结果

解题步骤：

N/A

注意事项：

Python代码：

# dp[i][j] = dp[i-1][j-1] + 1 if nums1[i-1] == nums2[j-1]
#          = 0                if nums1[i-1] != nums2[j-1]
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
	max_length = 0
	dp = [[0 for _ in range(len(nums2) + 1)] for _ in range(len(nums1) + 1)]
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if nums1[i - 1] == nums2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			max_length = max(max_length, dp[i][j])
	return max_length

算法分析：

时间复杂度为<code>O(n²)</code>，空间复杂度<code>O(n²)</code>