0718. 最长重复子数组 #
- 标签:数组、二分查找、动态规划、滑动窗口、哈希函数、滚动哈希
- 难度:中等
题目大意 #
给定两个整数数组 nums1
、nums2
。要求:计算两个数组中公共的、长度最长的子数组长度。
解题思路 #
动态规划求解。
定义状态 dp[i][j]
表示为:以下标 i - 1
结尾的 nums1
和以下标 j - 1
结尾的 nums2
的最长重复子数组长度。
两重遍历 nums1
、nums2
,计算 dp[i][j]
。
- 如果
nums1[i] == nums2[j]
,则当前元素可以构成公共子数组,则dp[i][j] = dp[i - 1][j - 1] + 1
。 - 如果
nums1[i] != nums2[j]
,则当前元素不能构成公共子数组,则dp[i][j] = 0
。
最后用 res
记录下最大的 dp[i][j]
即为答案。
代码 #
|
|