 暴力优化到 O(n) 动态规划)
LeetCode 1218「最长定差子序列」题解用值域哈希表把 O(N²) 暴力优化到 O(n) 动态规划【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇基于 leetcode 题解仓库中的1218 最长定差子序例题解完整还原这道动态规划题的求解路径先给出题目与约束再用 O(N²) 暴力枚举建立直觉随后推导以数值为键的哈希表 DP 并将复杂度压到 O(n)文中还通过对示例的逐步推演验证了重复值场景下的正确性并指出 difference 0 这一边界下原写法会低估结果、给出修正实现最后把该值域 DP模式推广到仓库中同源的 3041 题帮助读者掌握dp[数值] 最长链长这一通用套路。一、题目与约束条件原题1218. 最长定差子序列力扣中等难度题目解标注的面试出处为腾讯给你一个整数数组 arr 和一个整数 difference请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列并返回其中最长的等差子序列的长度。题目解原文给出的三组示例示例 1输入arr [1,2,3,4], difference 1输出4解释最长的等差子序列是[1,2,3,4]。示例 2输入arr [1,3,5,7], difference 1输出1解释最长的等差子序列是任意单个元素。示例 3输入arr [1,5,7,8,5,3,4,2,1], difference -2输出4解释最长的等差子序列是[7,5,3,1]。约束条件决定算法选型的关键信息1 arr.length 10^5 -10^4 arr[i], difference 10^4从约束中可以提炼出两点题目要求的是子序列subsequence而非子数组subarray元素在原数组中不必连续但必须保持原有先后顺序数组长度最高 10^5而元素值域只有[-10^4, 10^4]共 20001 个可能取值——值域远小于长度这正是后文用数值而不是下标作为 DP 状态键的依据。题目解标注的前置知识为数组与动态规划。二、暴力法枚举起点向后扫描题目解给出的最直观思路是暴力枚举出以每一个元素为开始元素的所有情况也就是对所有起点全部模拟一遍——这是暴力法的精髓先保证完备。这种解法会 TLE超时但顺着这个思维继续思考才能自然地引出优化方向。暴力法代码题目解原文Python3def longestSubsequence(self, arr: List[int], difference: int) - int: n len(arr) res 1 for i in range(n): count 1 for j in range(i 1, n): if arr[i] difference * count arr[j]: count 1 if count res: res count return res思路拆解对每个起点i令count记录从arr[i]出发已经接上的链长向后扫描j当且仅当arr[j]恰好等于等差链的第count项即arr[i] difference * count时count 1。由于链上的每一项取值都是确定的扫描遇到不匹配的元素只是跳过不影响后续匹配因此对每个起点都得到了一条最长定差子序列的长度取全局最大值res。复杂度题目解标注时间复杂度 $O(N^2)$、空间复杂度 $O(N)$。就这份实现而言两层循环共约 $N^2/2$ 次迭代当 $N 10^5$ 时达到 $10^{10}$ 量级必然超时另外从实现细节看代码额外使用的变量只有res、count与循环变量辅助空间实际上是 $O(1)$。三、动态规划把状态键从下标换成数值状态定义与转移方程题目解的核心想法是将以每一个元素结尾的最长等差子序列的长度统统存起来即dp[num] maxLen。这样遍历到一个新元素时就去之前的存储中查找dp[num - difference]如果找到了就更新dp[num] dp[num - difference] 1否则不做操作保持默认值 1。形式化地写状态dp[num]表示以值为 num 的元素结尾的最长定差子序列长度只保留以该值结尾的所有链中的最长者转移按原数组顺序扫描到num时dp[num] dp[num - difference] 1若num - difference此前出现过否则dp[num] 1答案max(dp.values())。为什么可以只按值记忆而丢掉下标链的合法性只依赖两个条件数值上恰好等于前驱值 difference以及前驱在数组中先出现。由于我们是从左到右单次扫描、遇到元素就立刻写表字典里任何一项dp[num - difference]都必然来自当前下标之前的某个位置顺序约束被按序扫描 查历史表这一结构天然满足无需在状态中记录下标。为什么能从 O(N²) 降到 O(n)这正是题目解所说的空间换时间暴力法中每个起点都要重新向后扫一遍每个状态被反复计算而哈希表把以某值结尾的最长链长缓存下来之后每个新元素只需一次 $O(1)$ 查表即可确定转移总时间 $O(n)$。这与仓库动态规划长文动态规划套路中状态转移 记忆化的主线一致把子问题的解存成表后续状态只做查表与更新。用示例 3 逐步推演以arr [1,5,7,8,5,3,4,2,1]、difference -2为例。此时查询键为num - difference num 2逐元素执行先置 1命中则覆盖为dp[num2] 1遍历元素 num查询键num 2查询结果更新后 dp[num]当前最大值13未命中dp[1] 1157未命中dp[5] 1179未命中dp[7] 11810未命中dp[8] 1157命中dp[7] 1dp[5] 2235命中dp[5] 2dp[3] 3346未命中dp[4] 1324命中dp[4] 1dp[2] 2313命中dp[3] 3dp[1] 44最终max(dp.values()) 4对应的正是解释中的[7,5,3,1]原数组下标 2、4、5、8。注意第二个5把dp[5]从 1 刷新为 2、随后的3又继承了这个 2——链是随着扫描逐步生长的这正是按序扫描 查历史表的威力每个元素只被处理一次却能把此前所有前驱的功劳都接过来。四、完整代码题目解给出的 Python3 实现原文保留class Solution: # 动态规划 def longestSubsequence(self, arr: List[int], difference: int) - int: n len(arr) res 1 dp {} for num in arr: dp[num] 1 if num - difference in dp: dp[num] dp[num - difference] 1 return max(dp.values())代码逐行说明dp {}以数值为键的哈希表即题目解强调的关键点——把以每一个元素结尾的最长等差子序列的长度统统存起来dp[num] 1每个元素先按自己单独成链初始化if num - difference in dp只有当前驱值确实先出现过时才能接链注意这里查的是num - difference而不是num difference——因为以 num 结尾的链其前一项的值必须是 num 减去公差return max(dp.values())最长链可能以任何一个值结尾取全部状态的极大值。五、复杂度分析与边界验证题目解给出的复杂度分析令 n 为数组长度时间复杂度$O(n)$——单次遍历每步两次 $O(1)$ 哈希操作空间复杂度$O(n)$——dp最多存 n 个键结合值域约束[-10^4, 10^4]实际键数上界为 $\min(n, 20001)$。边界 1重复值覆盖是否安全代码对同一个值反复执行先置 1、命中再覆盖会不会把之前算出的更长链抹掉不会。从实现结构看字典只增不删一旦num - difference进入过dp后续任何时刻它都还在且其值只增不减因此后一次对dp[num]的覆盖结果dp[num - difference] 1必然不小于前一次的值。先置 1在语义上只承担默认值的角色等价于dp[num] max(1, dp[num - difference] 1)的查表写法重复出现只会让链变得更长例如公差为 1 时重复的小数值会让后继元素接上更高的起点。边界 2difference 0 时原写法会低估修正写法约束允许difference 0此时答案应等于出现次数最多的值的次数。逐行推演题目解原代码在arr [3,3,3,0,3]、difference 0上的行为遍历元素执行过程dp 状态3第 1 个dp[3] 1查询键3 - 0 3刚被写入、必然命中 →dp[3] 2{3: 2}3第 2 个dp[3] 1被重置再命中自身 →dp[3] 2{3: 2}3第 3 个同上{3: 2}0dp[0] 1命中自身 →dp[0] 2{3: 2, 0: 2}3第 4 个dp[3] 1被重置再命中自身 →dp[3] 2{3: 2, 0: 2}原代码返回max 2而正确答案是4子序列[3,3,3,3]。原因在于difference 0时查询键就是num本身而代码先执行了dp[num] 1的无条件重置把正在累计的计数清零了。一个更稳健的等价写法是把重置与转移合并成一次赋值读取先于写入class Solution: def longestSubsequence(self, arr: List[int], difference: int) - int: dp {} for num in arr: dp[num] dp.get(num - difference, 0) 1 return max(dp.values())该写法在difference ≠ 0时与原解行为一致num - difference的键只会单调增长覆盖不会变差在difference 0时则退化为对每个值的自然计数dp[num] dp[num] 1两个场景都正确。六、模式推广同一套值域 DP在 3041 上的变体题目解把 3041. 修改数组后最大化数组中的连续元素数目 列为相关题目而该题解开头明确写道和 1218 类似——这正是本模式的一个变体同样将以每一个元素结尾的最长链长统统存起来dp[num]查询dp[num - 1]即公差固定为 1的特例不同点一3041 要求选出元素排序后连续对原顺序没有要求因此可以先排序再扫描不同点二由于元素可以至多 1当前元素既可当作链尾、也可当作链尾的前一项所以题解在更新dp[num]之外还要额外维护dp[num 1] memo[num] 1才能保证状态完备复杂度瓶颈变为排序时间 $O(n \log n)$、空间 $O(n)$。对照两题可以看出本套路的抽象形态当转移关系是值 → 值而非位置 → 位置、且值域可哈希时用哈希表按值存dp把双层循环压缩成单次扫描。1218 中公差任意、顺序敏感所以按原序扫描即可3041 中公差为 1、顺序不敏感所以排序后扫描并补一个前向一格的状态。七、该题解在仓库中的位置题解正文problems/1218.longest-arithmetic-subsequence-of-given-difference.md其章节组织题目地址 / 题目描述 / 前置知识 / 公司 / 思路 / 关键点解析 / 代码 / 相关题目与仓库题解模板要求的格式一致收录位置1218 作为中等难度题被收录在中等难度题目清单中1218. 最长定差子序列条目交叉引用3041 题解的相关题目一节反向链接回 1218两篇题解互相印证同一模式理论背景仓库中的动态规划长文对状态、转移、记忆化递归与 DP 的关系做了系统讲解可作为本篇第三节的延伸阅读。八、关键点小结暴力法枚举每个起点向后扫描等差链完备但 $O(N^2)$在 $N 10^5$ 约束下必然 TLE状态设计dp[num] 以值为num的元素结尾的最长定差子序列长度——利用值域远小于长度与转移只依赖值两个特点把状态键从下标换成数值转移方向查的是dp[num - difference]前驱值按原数组顺序单次扫描即可保证顺序约束复杂度时间 $O(n)$、空间 $O(n)$键数上界 $\min(n, 20001)$边界提醒difference 0时先置 1 再转移的写法会重置计数导致低估推荐合并为dp[num] dp.get(num - difference, 0) 1套路迁移同模式可直接套用到 3041公差固定为 1、可先排序、需额外维护dp[num 1]。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 1218「最长定差子序列」题解：用值域哈希表把 O(N²) 暴力优化到 O(n) 动态规划
LeetCode 1218「最长定差子序列」题解用值域哈希表把 O(N²) 暴力优化到 O(n) 动态规划【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇基于 leetcode 题解仓库中的1218 最长定差子序例题解完整还原这道动态规划题的求解路径先给出题目与约束再用 O(N²) 暴力枚举建立直觉随后推导以数值为键的哈希表 DP 并将复杂度压到 O(n)文中还通过对示例的逐步推演验证了重复值场景下的正确性并指出 difference 0 这一边界下原写法会低估结果、给出修正实现最后把该值域 DP模式推广到仓库中同源的 3041 题帮助读者掌握dp[数值] 最长链长这一通用套路。一、题目与约束条件原题1218. 最长定差子序列力扣中等难度题目解标注的面试出处为腾讯给你一个整数数组 arr 和一个整数 difference请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列并返回其中最长的等差子序列的长度。题目解原文给出的三组示例示例 1输入arr [1,2,3,4], difference 1输出4解释最长的等差子序列是[1,2,3,4]。示例 2输入arr [1,3,5,7], difference 1输出1解释最长的等差子序列是任意单个元素。示例 3输入arr [1,5,7,8,5,3,4,2,1], difference -2输出4解释最长的等差子序列是[7,5,3,1]。约束条件决定算法选型的关键信息1 arr.length 10^5 -10^4 arr[i], difference 10^4从约束中可以提炼出两点题目要求的是子序列subsequence而非子数组subarray元素在原数组中不必连续但必须保持原有先后顺序数组长度最高 10^5而元素值域只有[-10^4, 10^4]共 20001 个可能取值——值域远小于长度这正是后文用数值而不是下标作为 DP 状态键的依据。题目解标注的前置知识为数组与动态规划。二、暴力法枚举起点向后扫描题目解给出的最直观思路是暴力枚举出以每一个元素为开始元素的所有情况也就是对所有起点全部模拟一遍——这是暴力法的精髓先保证完备。这种解法会 TLE超时但顺着这个思维继续思考才能自然地引出优化方向。暴力法代码题目解原文Python3def longestSubsequence(self, arr: List[int], difference: int) - int: n len(arr) res 1 for i in range(n): count 1 for j in range(i 1, n): if arr[i] difference * count arr[j]: count 1 if count res: res count return res思路拆解对每个起点i令count记录从arr[i]出发已经接上的链长向后扫描j当且仅当arr[j]恰好等于等差链的第count项即arr[i] difference * count时count 1。由于链上的每一项取值都是确定的扫描遇到不匹配的元素只是跳过不影响后续匹配因此对每个起点都得到了一条最长定差子序列的长度取全局最大值res。复杂度题目解标注时间复杂度 $O(N^2)$、空间复杂度 $O(N)$。就这份实现而言两层循环共约 $N^2/2$ 次迭代当 $N 10^5$ 时达到 $10^{10}$ 量级必然超时另外从实现细节看代码额外使用的变量只有res、count与循环变量辅助空间实际上是 $O(1)$。三、动态规划把状态键从下标换成数值状态定义与转移方程题目解的核心想法是将以每一个元素结尾的最长等差子序列的长度统统存起来即dp[num] maxLen。这样遍历到一个新元素时就去之前的存储中查找dp[num - difference]如果找到了就更新dp[num] dp[num - difference] 1否则不做操作保持默认值 1。形式化地写状态dp[num]表示以值为 num 的元素结尾的最长定差子序列长度只保留以该值结尾的所有链中的最长者转移按原数组顺序扫描到num时dp[num] dp[num - difference] 1若num - difference此前出现过否则dp[num] 1答案max(dp.values())。为什么可以只按值记忆而丢掉下标链的合法性只依赖两个条件数值上恰好等于前驱值 difference以及前驱在数组中先出现。由于我们是从左到右单次扫描、遇到元素就立刻写表字典里任何一项dp[num - difference]都必然来自当前下标之前的某个位置顺序约束被按序扫描 查历史表这一结构天然满足无需在状态中记录下标。为什么能从 O(N²) 降到 O(n)这正是题目解所说的空间换时间暴力法中每个起点都要重新向后扫一遍每个状态被反复计算而哈希表把以某值结尾的最长链长缓存下来之后每个新元素只需一次 $O(1)$ 查表即可确定转移总时间 $O(n)$。这与仓库动态规划长文动态规划套路中状态转移 记忆化的主线一致把子问题的解存成表后续状态只做查表与更新。用示例 3 逐步推演以arr [1,5,7,8,5,3,4,2,1]、difference -2为例。此时查询键为num - difference num 2逐元素执行先置 1命中则覆盖为dp[num2] 1遍历元素 num查询键num 2查询结果更新后 dp[num]当前最大值13未命中dp[1] 1157未命中dp[5] 1179未命中dp[7] 11810未命中dp[8] 1157命中dp[7] 1dp[5] 2235命中dp[5] 2dp[3] 3346未命中dp[4] 1324命中dp[4] 1dp[2] 2313命中dp[3] 3dp[1] 44最终max(dp.values()) 4对应的正是解释中的[7,5,3,1]原数组下标 2、4、5、8。注意第二个5把dp[5]从 1 刷新为 2、随后的3又继承了这个 2——链是随着扫描逐步生长的这正是按序扫描 查历史表的威力每个元素只被处理一次却能把此前所有前驱的功劳都接过来。四、完整代码题目解给出的 Python3 实现原文保留class Solution: # 动态规划 def longestSubsequence(self, arr: List[int], difference: int) - int: n len(arr) res 1 dp {} for num in arr: dp[num] 1 if num - difference in dp: dp[num] dp[num - difference] 1 return max(dp.values())代码逐行说明dp {}以数值为键的哈希表即题目解强调的关键点——把以每一个元素结尾的最长等差子序列的长度统统存起来dp[num] 1每个元素先按自己单独成链初始化if num - difference in dp只有当前驱值确实先出现过时才能接链注意这里查的是num - difference而不是num difference——因为以 num 结尾的链其前一项的值必须是 num 减去公差return max(dp.values())最长链可能以任何一个值结尾取全部状态的极大值。五、复杂度分析与边界验证题目解给出的复杂度分析令 n 为数组长度时间复杂度$O(n)$——单次遍历每步两次 $O(1)$ 哈希操作空间复杂度$O(n)$——dp最多存 n 个键结合值域约束[-10^4, 10^4]实际键数上界为 $\min(n, 20001)$。边界 1重复值覆盖是否安全代码对同一个值反复执行先置 1、命中再覆盖会不会把之前算出的更长链抹掉不会。从实现结构看字典只增不删一旦num - difference进入过dp后续任何时刻它都还在且其值只增不减因此后一次对dp[num]的覆盖结果dp[num - difference] 1必然不小于前一次的值。先置 1在语义上只承担默认值的角色等价于dp[num] max(1, dp[num - difference] 1)的查表写法重复出现只会让链变得更长例如公差为 1 时重复的小数值会让后继元素接上更高的起点。边界 2difference 0 时原写法会低估修正写法约束允许difference 0此时答案应等于出现次数最多的值的次数。逐行推演题目解原代码在arr [3,3,3,0,3]、difference 0上的行为遍历元素执行过程dp 状态3第 1 个dp[3] 1查询键3 - 0 3刚被写入、必然命中 →dp[3] 2{3: 2}3第 2 个dp[3] 1被重置再命中自身 →dp[3] 2{3: 2}3第 3 个同上{3: 2}0dp[0] 1命中自身 →dp[0] 2{3: 2, 0: 2}3第 4 个dp[3] 1被重置再命中自身 →dp[3] 2{3: 2, 0: 2}原代码返回max 2而正确答案是4子序列[3,3,3,3]。原因在于difference 0时查询键就是num本身而代码先执行了dp[num] 1的无条件重置把正在累计的计数清零了。一个更稳健的等价写法是把重置与转移合并成一次赋值读取先于写入class Solution: def longestSubsequence(self, arr: List[int], difference: int) - int: dp {} for num in arr: dp[num] dp.get(num - difference, 0) 1 return max(dp.values())该写法在difference ≠ 0时与原解行为一致num - difference的键只会单调增长覆盖不会变差在difference 0时则退化为对每个值的自然计数dp[num] dp[num] 1两个场景都正确。六、模式推广同一套值域 DP在 3041 上的变体题目解把 3041. 修改数组后最大化数组中的连续元素数目 列为相关题目而该题解开头明确写道和 1218 类似——这正是本模式的一个变体同样将以每一个元素结尾的最长链长统统存起来dp[num]查询dp[num - 1]即公差固定为 1的特例不同点一3041 要求选出元素排序后连续对原顺序没有要求因此可以先排序再扫描不同点二由于元素可以至多 1当前元素既可当作链尾、也可当作链尾的前一项所以题解在更新dp[num]之外还要额外维护dp[num 1] memo[num] 1才能保证状态完备复杂度瓶颈变为排序时间 $O(n \log n)$、空间 $O(n)$。对照两题可以看出本套路的抽象形态当转移关系是值 → 值而非位置 → 位置、且值域可哈希时用哈希表按值存dp把双层循环压缩成单次扫描。1218 中公差任意、顺序敏感所以按原序扫描即可3041 中公差为 1、顺序不敏感所以排序后扫描并补一个前向一格的状态。七、该题解在仓库中的位置题解正文problems/1218.longest-arithmetic-subsequence-of-given-difference.md其章节组织题目地址 / 题目描述 / 前置知识 / 公司 / 思路 / 关键点解析 / 代码 / 相关题目与仓库题解模板要求的格式一致收录位置1218 作为中等难度题被收录在中等难度题目清单中1218. 最长定差子序列条目交叉引用3041 题解的相关题目一节反向链接回 1218两篇题解互相印证同一模式理论背景仓库中的动态规划长文对状态、转移、记忆化递归与 DP 的关系做了系统讲解可作为本篇第三节的延伸阅读。八、关键点小结暴力法枚举每个起点向后扫描等差链完备但 $O(N^2)$在 $N 10^5$ 约束下必然 TLE状态设计dp[num] 以值为num的元素结尾的最长定差子序列长度——利用值域远小于长度与转移只依赖值两个特点把状态键从下标换成数值转移方向查的是dp[num - difference]前驱值按原数组顺序单次扫描即可保证顺序约束复杂度时间 $O(n)$、空间 $O(n)$键数上界 $\min(n, 20001)$边界提醒difference 0时先置 1 再转移的写法会重置计数导致低估推荐合并为dp[num] dp.get(num - difference, 0) 1套路迁移同模式可直接套用到 3041公差固定为 1、可先排序、需额外维护dp[num 1]。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考