LeetCode 1143 & 718：最长公共子序列 / 最长重复子数组

LeetCode 1143 & 718：最长公共子序列 / 最长重复子数组 —— 联合题解 ✅

这两道题 名字很像、状态转移很像，但有一个 致命区别： 👉 是否要求连续。

下面我把它们 放在一张笔记里，一次讲透。

📌 题目列表

📖 内容概要

给定两个数组 / 字符串，求它们的 最长公共部分。

• 1143：字符可以不连续
• 718：字符必须连续

✅ 二维 DP ✅ 面试超级高频 ✅ 经典模板题

💡 统一 DP 定义

dp[i][j] =
第一个数组前 i 个元素（以i–1结尾）
与第二个数组前 j 个元素（以j–1结尾）
的最长公共长度

✅ 使用 i、j 从 1 开始 ✅ 方便处理边界

🔁 状态转移（核心区别）

✅ 1143：最长公共子序列（不连续）

if (text1[i–1] == text2[j–1]) {
dp[i][j] = dp[i–1][j–1] + 1;
} else {
dp[i][j] = max(dp[i–1][j], dp[i][j–1]);
}

✅ 不相等时：

• 可以跳过 text1[i]
• 也可以跳过 text2[j]

✅ 718：最长重复子数组（连续）

if (nums1[i–1] == nums2[j–1]) {
dp[i][j] = dp[i–1][j–1] + 1;
} else {
dp[i][j] = 0; // 必须连续，断了就归零
}

✅ 不相等时：

• 不能继承其他状态
• 必须重新计数

✅ 1143 题：最长公共子序列（AC 代码）

class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
char[] t1 = text1.toCharArray();
char[] t2 = text2.toCharArray();

int[][] dp = new int[len1 + 1][len2 + 1];
int res = 0;

for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (t1[i – 1] == t2[j – 1]) {
dp[i][j] = dp[i – 1][j – 1] + 1;
} else {
dp[i][j] = Math.max(dp[i – 1][j], dp[i][j – 1]);
}
res = Math.max(res, dp[i][j]);
}
}
return res;
}
}

✅ 718 题：最长重复子数组（AC 代码）

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

for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (nums1[i – 1] == nums2[j – 1]) {
dp[i][j] = dp[i – 1][j – 1] + 1;
} else {
dp[i][j] = 0;
}
res = Math.max(res, dp[i][j]);
}
}
return res;
}
}

🔍 两题核心对比表（必背）

⏱️ 复杂度分析

✅ 一句话总结

LCS 是“可以不连续，断了还能接”； 最长重复子数组是“必须连续，断了就重来”。

📌 面试加分点（建议记住）

• ✅ 为什么 LCS 要继承两个方向？
• ✅ 为什么子数组必须归零？
• ✅ 如何用滚动数组优化空间？
• ✅ 和编辑距离的关系