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

LeetCode 1143 718最长公共子序列 / 最长重复子数组 —— 联合题解 ✅这两道题名字很像、状态转移很像但有一个致命区别是否要求连续。下面我把它们放在一张笔记里一次讲透。 题目列表题号题目是否连续1143最长公共子序列LCS❌ 不要求连续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){intlen1text1.length();intlen2text2.length();char[]t1text1.toCharArray();char[]t2text2.toCharArray();int[][]dpnewint[len11][len21];intres0;for(inti1;ilen1;i){for(intj1;jlen2;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]);}resMath.max(res,dp[i][j]);}}returnres;}}✅ 718 题最长重复子数组AC 代码classSolution{publicintfindLength(int[]nums1,int[]nums2){intlen1nums1.length;intlen2nums2.length;int[][]dpnewint[len11][len21];intres0;for(inti1;ilen1;i){for(intj1;jlen2;j){if(nums1[i-1]nums2[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]0;}resMath.max(res,dp[i][j]);}}returnres;}} 两题核心对比表必背对比项1143LCS718子数组是否连续❌✅相等时dp[i-1][j-1] 1dp[i-1][j-1] 1不相等时max(dp[i-1][j], dp[i][j-1])0时间复杂度O(n²)O(n²)⏱️ 复杂度分析指标复杂度时间复杂度O(len1 × len2)空间复杂度O(len1 × len2)✅ 一句话总结LCS 是“可以不连续断了还能接”最长重复子数组是“必须连续断了就重来”。 面试加分点建议记住✅ 为什么 LCS 要继承两个方向✅ 为什么子数组必须归零✅ 如何用滚动数组优化空间✅ 和编辑距离的关系