LeetCode 718. 最长重复子数组

约 5 分钟
文章信息 15 个分类 6 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 50-100 腾讯 字节 阿里 微软 美团 京东 百度 快手 虾皮
标签
数组 动态规划 二分查找 滑动窗口 哈希函数 滚动哈希

题目描述

✅ 718. 最长重复子数组

image-20260928194102049

题意分析

给定两个整数数组，找出同时出现在两个数组中的最长连续片段，返回它的长度。两个片段可以出现在不同的起始下标，但对应元素必须逐个相等，而且在各自数组里都不能跳过元素。

本题求的是公共子数组，不是允许跳过元素的公共子序列，也不是统计公共数值的种类或数量。只需返回最长长度，不必返回片段本身；如果没有相同元素，答案为 0。

解法：滚动动态规划匹配连续后缀

核心思路

[!blue]

连续片段必须同时向两边的前一个位置延伸，所以先固定它在两个数组中的结束位置。令 D[i][j] 表示以 nums1[i - 1] 和 nums2[j - 1] 结尾的最长公共连续后缀长度。这里的 i、j 从 1 开始，多出的第 0 行和第 0 列表示空前缀，长度都是 0。

若两个末尾元素相等，去掉它们后，剩余匹配必须恰好结束在各自前一个位置。因此最优长度为 D[i - 1][j - 1] + 1；反过来，把这对相等元素接到前一个公共后缀上，也一定能构成合法连续片段。若末尾元素不等，任何非空公共后缀都不可能同时以它们结尾，所以当前状态必须置为 0，不能跳过其中一个元素继续取左边或上边的最优值。

转移只依赖上一行的左上角，可以把二维状态压缩为一行 dp。处理 nums1[i - 1] 时，内层让 j 从右向左移动；此时 dp[j - 1] 尚未更新，仍代表上一行的 D[i - 1][j - 1]。写入 dp[j] 后不再需要它原来的值，因此可以安全覆盖。若反过来从左向右，会错误地读取同一行刚产生的状态。

状态要求片段恰好在指定位置结束，而最长公共片段可能在任意一对位置结束，不一定触及两个数组末尾。因此还要用独立的 ans 记录所有状态的最大值。每个公共连续片段都有确定的两个结束位置，遍历全部状态就不会漏掉最优答案。

解题步骤

  1. 创建长度为 nums2.length + 1 的零数组 dp，并令答案 ans = 0；dp[0] 始终保持为零边界。
  2. 外层用 i 从 1 到 nums1.length 枚举第一个数组的结束位置。
  3. 内层用 j 从 nums2.length 倒序到 1，比较 nums1[i - 1] 与 nums2[j - 1]。
  4. 相等时令 dp[j] = dp[j - 1] + 1 并更新全局最大值，不相等时令 dp[j] = 0。
  5. 全部位置处理完后返回 ans，而不是最后一次更新的某个后缀状态。

代码实现

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length + 1];
        int ans = 0;

        for (int i = 1; i <= nums1.length; i++) {
            // 倒序更新，左侧位置仍保留上一行的旧对角状态。
            for (int j = nums2.length; j >= 1; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                    ans = Math.max(ans, dp[j]);
                } else {
                    // 当前元素失配，连续公共后缀必须在这里中断。
                    dp[j] = 0;
                }
            }
        }

        return ans;
    }
}

func findLength(nums1 []int, nums2 []int) int {
    dp := make([]int, len(nums2)+1)
    ans := 0

    for i := 1; i <= len(nums1); i++ {
        // 倒序更新，左侧位置仍保留上一行的旧对角状态。
        for j := len(nums2); j >= 1; j-- {
            if nums1[i-1] == nums2[j-1] {
                dp[j] = dp[j-1] + 1
                if dp[j] > ans {
                    ans = dp[j]
                }
            } else {
                // 当前元素失配，连续公共后缀必须在这里中断。
                dp[j] = 0
            }
        }
    }

    return ans
}

复杂度分析

  • 时间复杂度：$O(mn)$，m、n 为两个数组长度，每对结束位置计算一次。
  • 空间复杂度：$O(n)$，一维数组保存第二个数组方向的状态，另有常数个变量。

关键点总结

[!green]

  • 固定两个结束位置，把连续要求转化为“只能从左上角延长”的递推。
  • 当前元素不等就没有非空公共后缀，必须清零，不能沿用旧答案。
  • 一维压缩时倒序更新，确保读到上一行尚未覆盖的左上角状态。
  • 后缀长度与全局最长长度分开保存，答案可以出现在任意中间位置。

易错点总结

[!yellow]

  • 失配时不清零，会让之前的匹配跨过不相等元素，被后面的状态接成不连续的片段。
  • 使用公共子序列的“取左边与上边最大值”转移，允许跳过元素，不再符合子数组连续的要求。
  • 一维数组从左向右更新，会用本行新状态延长，可能让同一个数组位置被重复匹配。
  • 只返回 dp[n]，只能得到以最后一对元素结尾的后缀长度，可能漏掉中途已经结束的最长片段。
  • 状态下标对应前缀长度，访问实际元素时必须减一，否则会错位并可能越界。

相似题目

题目 难度 关联与区别
1143. 最长公共子序列 中等 原题允许跳过元素，本题必须连续，因此失配时当前共同后缀长度归零。
补充题 157. 最长公共子串的构造 中等 都用相等时递增长公共后缀的 DP；补充题记录最佳结束位置以还原字符串。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/15544319
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！