0718. 最长重复子数组 #
- 标签:数组、二分查找、动态规划、滑动窗口、哈希函数、滚动哈希
- 难度:中等
题目大意 #
描述:给定两个整数数组 $nums1$、$nums2$。
要求:计算两个数组中公共的、长度最长的子数组长度。
说明:
- $1 \le nums1.length, nums2.length \le 1000$。
- $0 \le nums1[i], nums2[i] \le 100$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:暴力(超时) #
- 枚举数组 $nums1$ 和 $nums2$ 的子数组开始位置 $i$、$j$。
- 如果遇到相同项,即 $nums1[i] == nums2[j]$,则以 $nums1[i]$、$nums2[j]$ 为前缀,同时向后遍历,计算当前的公共子数组长度 $subLen$ 最长为多少。
- 直到遇到超出数组范围或者 $nums1[i + subLen] == nums2[j + subLen]$ 情况时,停止遍历,并更新答案。
- 继续执行 $1 \sim 3$ 步,直到遍历完,输出答案。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n \times m \times min(n, m))$。其中 $n$ 是数组 $nums1$ 的长度,$m$ 是数组 $nums2$ 的长度。
- 空间复杂度:$O(1)$。
思路 2:滑动窗口 #
暴力方法中,因为子数组在两个数组中的位置不同,所以会导致子数组之间会进行多次比较。
我们可以将两个数组分别看做是两把直尺。然后将数组 $nums1$ 固定, 让 $nums2$ 的尾部与 $nums1$ 的头部对齐,如下所示。
|
|
然后逐渐向右移动直尺 $nums2$,比较 $nums1$ 与 $nums2$ 重叠部分中的公共子数组的长度,直到直尺 $nums2$ 的头部移动到 $nums1$ 的尾部。
|
|
在这个过程中求得的 $nums1$ 与 $nums2$ 重叠部分中的最大的公共子数组的长度就是 $nums1$ 与 $nums2$ 数组中公共的、长度最长的子数组长度。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n + m) \times min(n, m)$。其中 $n$ 是数组 $nums1$ 的长度,$m$ 是数组 $nums2$ 的长度。
- 空间复杂度:$O(1)$。
思路 3:动态规划 #
1. 划分阶段 #
按照子数组结尾位置进行阶段划分。
2. 定义状态 #
定义状态 $dp[i][j]$ 为:「以 $nums1$ 中前 $i$ 个元素为子数组($nums1[0]…nums2[i - 1]$)」和「以 $nums2$ 中前 $j$ 个元素为子数组($nums2[0]…nums2[j - 1]$)」的最长公共子数组长度。
3. 状态转移方程 #
- 如果 $nums1[i - 1] = nums2[j - 1]$,则当前元素可以构成公共子数组,此时 $dp[i][j] = dp[i - 1][j - 1] + 1$。
- 如果 $nums1[i - 1] \ne nums2[j - 1]$,则当前元素不能构成公共子数组,此时 $dp[i][j] = 0$。
4. 初始条件 #
- 当 $i = 0$ 时,$nums1[0]…nums1[i - 1]$ 表示的是空数组,空数组与 $nums2[0]…nums2[j - 1]$ 的最长公共子序列长度为 $0$,即 $dp[0][j] = 0$。
- 当 $j = 0$ 时,$nums2[0]…nums2[j - 1]$ 表示的是空数组,空数组与 $nums1[0]…nums1[i - 1]$ 的最长公共子序列长度为 $0$,即 $dp[i][0] = 0$。
5. 最终结果 #
- 根据状态定义, $dp[i][j]$ 为:「以 $nums1$ 中前 $i$ 个元素为子数组($nums1[0]…nums2[i - 1]$)」和「以 $nums2$ 中前 $j$ 个元素为子数组($nums2[0]…nums2[j - 1]$)」的最长公共子数组长度。在遍历过程中,我们可以使用 $res$ 记录下所有 $dp[i][j]$ 中最大值即为答案。
思路 3:代码 #
|
|
思路 3:复杂度分析 #
- 时间复杂度:$O(n \times m)$。其中 $n$ 是数组 $nums1$ 的长度,$m$ 是数组 $nums2$ 的长度。
- 空间复杂度:$O(n \times m)$。