LeetCode 718. 最长重复子数组

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

题目描述

✅ 718. 最长重复子数组

image-20250418154831412

题意分析

给定两个整数数组 nums1 和 nums2，返回两个数组中公共的、长度最长的子数组的长度。

关键在于「子数组」二字：它要求元素在两个数组中都连续出现，这与「子序列」（可以跳着选）完全不同。以官方样例 nums1 = [1,2,3,2,1]、nums2 = [3,2,1,4,7] 为例，公共子序列可以东拼西凑，但公共子数组必须是一段原封不动的连续片段——[3,2,1] 在两边都连续出现，答案是 3。

「连续」意味着一旦某个位置对不上，之前积累的匹配对后面毫无帮助——这是本题与子序列类问题在状态设计上分道扬镳的根源。

边界方面：两数组长度均至少为 1，但完全可能没有任何公共元素，此时答案为 0；答案不会超过两数组长度的较小值。

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

核心思路

问题关键：题目求的是连续子数组。两个位置不相等时，之前的匹配不能跳过当前元素继续，长度必须归零。

定义 dp[i][j] 表示以 nums1[i - 1]、nums2[j - 1] 结尾的最长公共子数组长度。两元素相等时，dp[i][j] = dp[i - 1][j - 1] + 1；不等时为 0。最长片段可能结束在任意位置，所以遍历时维护全局最大值。

转移只依赖左上角，可以压缩成一维数组。不变量：更新 dp[j] 时，dp[j - 1] 必须仍是上一行的值，因此内层必须从右向左。这样每个非零状态都对应一条连续相等的对角线，取其中最大值就是答案。

解题步骤

  1. 建立长度为 nums2.length + 1 的 dp，多出的 dp[0] = 0 作为边界。
  2. 外层从左到右枚举 nums1，内层从右到左枚举 nums2。
  3. 两元素相等时令 dp[j] = dp[j - 1] + 1，并更新答案；不相等时令 dp[j] = 0。
  4. 返回遍历期间的最大值。样例中的 [3,2,1] 对应三格连续递增的对角线 1 → 2 → 3。

代码实现

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)$，一维数组保存 nums2 方向的状态。

关键点总结

  • 「连续」决定了状态必须表示“以当前位置结尾”，且不相等时必须清零。
  • 一维压缩后要倒序更新，保证读取的是上一行的左上角状态。
  • 答案是所有结尾状态的最大值，不一定在 dp 的最后一格。
  • 二分长度加滚动哈希可以降低渐进复杂度，但有碰撞成本；面试主解法优先写清晰稳定的 DP。

易错点总结

  • 不相等时不清零：[1,2,3] 与 [1,4,3] 会把不连续的 1、3 拼在一起。
  • 一维数组从左向右更新：dp[j - 1] 已是本行新值，会在同一行错误累加。
  • 返回 dp[n]：[3,2,1,4] 与 [3,2,1,7] 的最长片段结束在中间，末格是 0。
  • 比较 nums1[i] 与 nums2[j]：状态下标多开了一位，实际元素下标应分别减一。

相似题目

题目 难度 考察点
1143. 最长公共子序列 中等 子序列版对照：断开可继承，转移多出两个方向的 max
1035. 不相交的线 中等 1143 的换皮题，练习把新题面翻译回 LCS 模型
674. 最长连续递增序列 简单 单数组版「断了清零」，同为以结尾定义状态
53. 最大子数组和 中等 「以 i 结尾」状态设计加全局取最大的同款套路