最长重复子数组

Maximum Length of Repeated Subarray

问题：最长重复子数组

考察：数组、动态规划

来源：Citadel

链接：https://www.jointaro.com/interviews/questions/maximum-length-of-repeated-subarray/

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

Example 1:

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].

Example 2:

Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5
Explanation: The repeated subarray with maximum length is [0,0,0,0,0].

Constraints:

解析

思路：令 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的公共子数组长度。若两数相等则由 dp[i-1][j-1]+1 转移，并维护最大值。

复杂度：时间 O(mn)，空间 O(n) 可滚动优化。