#718.最长重复子数组

LeetCode 原题链接

#1.dp 数组含义

定义二维数组 dp：

dp[i][j] 表示以 nums1[i - 1] 结尾、以 nums2[j - 1] 结尾的最长重复子数组长度。

注意这里的 i 和 j 表示的是“前几个元素”，不是数组下标。

例如：

dp[3][4]

表示：

以 nums1[2] 结尾、以 nums2[3] 结尾的最长重复子数组长度。

这道题要求的是“子数组”，子数组必须连续。

所以 dp[i][j] 只关心两个数组当前结尾位置能向前连续匹配多长，而不是像最长公共子序列那样可以跳着选。

题目要求整个数组中的最长重复子数组长度，所以最终答案需要在计算过程中维护一个最大值：

maxLen

#2. 确定状态转移方程

计算 dp[i][j] 时，需要比较两个当前结尾元素：

nums1[i - 1]
nums2[j - 1]

#当前元素相同

如果：

nums1[i - 1] === nums2[j - 1]

说明这两个元素可以作为重复子数组的最后一个元素。

此时重复子数组的长度，等于前一个位置的连续匹配长度再加 1：

dp[i][j] = dp[i - 1][j - 1] + 1;

也就是：

前面已经连续匹配了 dp[i - 1][j - 1] 个元素，
现在 nums1[i - 1] 和 nums2[j - 1] 又相等，
所以连续长度可以加 1。

#当前元素不同

如果：

nums1[i - 1] !== nums2[j - 1]

说明以这两个元素结尾时，无法形成公共的连续子数组。

所以：

dp[i][j] = 0;

这也是“最长重复子数组”和“最长公共子序列”的重要区别。

子数组必须连续，一旦当前结尾元素不相等，连续匹配就断了，不能从 dp[i - 1][j] 或 dp[i][j - 1] 转移。

完整转移方程：

if (nums1[i - 1] === nums2[j - 1]) {
  dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
  dp[i][j] = 0;
}

#3.dp 数组如何初始化

因为 dp[i][j] 表示以某两个元素结尾的最长重复子数组长度，所以需要处理空前缀。

dp[0][j] = 0：

nums1 的前 0 个元素是空数组，和 nums2 的任意前缀都没有重复子数组。

dp[i][0] = 0：

nums2 的前 0 个元素是空数组，和 nums1 的任意前缀都没有重复子数组。

因此可以创建一个 (nums1.length + 1) * (nums2.length + 1) 的二维数组，并全部初始化为 0：

const dp = Array.from({ length: nums1.length + 1 }, () =>
  new Array(nums2.length + 1).fill(0)
);

这样后续计算 dp[i][j] 时，可以安全访问 dp[i - 1][j - 1]。

如果 nums1 或 nums2 是空数组，最终答案自然就是 0。

#4. 确定遍历顺序

根据状态转移方程：

dp[i][j] 依赖 dp[i - 1][j - 1]

也就是当前格子只依赖左上方的状态。

所以按行从上到下、每一行从左到右遍历即可：

for (let i = 1; i <= nums1.length; i++) {
  for (let j = 1; j <= nums2.length; j++) {
    // 计算 dp[i][j]
  }
}

这样计算 dp[i][j] 时，左上方的 dp[i - 1][j - 1] 一定已经计算完成。

#5. 举例打印dp 数组

以：

nums1 = [1, 2, 3, 2, 1]
nums2 = [3, 2, 1, 4, 7]

为例。

行表示 nums1 的前缀，列表示 nums2 的前缀：

#填第 1 行：nums1[0] = 1

和 nums2 中每个元素比较：

• 1 !== 3，dp[1][1] = 0
• 1 !== 2，dp[1][2] = 0
• 1 === 1，dp[1][3] = dp[0][2] + 1 = 1
• 1 !== 4，dp[1][4] = 0
• 1 !== 7，dp[1][5] = 0

#填完整张表

最终 dp 数组为：

其中最大值是：

dp[5][3] = 3

对应的最长重复子数组是：

[3, 2, 1]

所以返回 3。

#6. 代码实现

var findLength = function (nums1, nums2) {
  const m = nums1.length;
  const n = nums2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  let maxLen = 0;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (nums1[i - 1] === nums2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        maxLen = Math.max(maxLen, dp[i][j]);
      }
    }
  }

  return maxLen;
};

#复杂度分析

• 时间复杂度：O(m * n)，其中 m 是 nums1 的长度，n 是 nums2 的长度。
• 空间复杂度：O(m * n)，需要一个二维 dp 数组保存状态。