企业官网建设流程全解析

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 代码）

classSolution{publicintlongestCommonSubsequence(Stringtext1,Stringtext2){intlen1=text1.length();intlen2=text2.length();char[]t1=text1.toCharArray();char[]t2=text2.toCharArray();int[][]dp=newint[len1+1][len2+1];intres=0;for(inti=1;i<=len1;i++){for(intj=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]);}}returnres;}}

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

classSolution{publicintfindLength(int[]nums1,int[]nums2){intlen1=nums1.length;intlen2=nums2.length;int[][]dp=newint[len1+1][len2+1];intres=0;for(inti=1;i<=len1;i++){for(intj=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]);}}returnres;}}

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

⏱️ 复杂度分析

✅ 一句话总结

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

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

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