LeetCode 873 最长的斐波那契子序列的长度集合枚举与动态规划双解法剖析【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文以 LeetCode 873「最长的斐波那契子序列的长度」为案例完整解析如何在一个严格递增的正整数数组中找出满足X_i X_{i1} X_{i2}的最长斐波那契式子序列。文章以仓库中 problems/873.length-of-longest-fibonacci-subsequence.md 的解题思路为主线从题目定义、集合枚举法、代码实现到复杂度分析层层展开并结合本仓库的 动态规划专题 梳理最优子结构与无后效性等前置概念。读完本文你将掌握「枚举两两起点 集合查表延伸」这一 O(n²log) 解法并理解如何借助哈希索引将时间复杂度进一步优化到 O(n²)。题目定义与样例分析斐波那契式的定义如果序列X_1, X_2, ..., X_n满足下列条件就说它是斐波那契式的n 3 对于所有 i 2 n都有 X_i X_{i1} X_{i2}题目给定一个严格递增的正整数数组 A要求找到 A 中最长的斐波那契式子序列的长度如果不存在返回0。子序列是从原序列 A 中派生出来的从 A 中删掉任意数量的元素也可以不删而不改变其余元素的顺序。例如[3, 5, 8]是[3, 4, 5, 6, 7, 8]的一个子序列。注意三个关键约束子序列不要求连续只要求保持相对顺序数组严格递增且均为正整数这保证了斐波那契式序列在数组内的唯一延伸方向3 A.length 10001 A[0] A[1] ... A[A.length - 1] 10^9。示例拆解示例 1输入: [1,2,3,4,5,6,7,8] 输出: 5 解释: 最长的斐波那契式子序列为[1,2,3,5,8]从1, 2出发延伸为1, 2, 3, 5, 8长度为 5注意数组虽然包含4和6、7但子序列1,2,3,5,8跳过了它们恰好印证了「子序列不要求连续」。示例 2输入: [1,3,7,11,12,14,18] 输出: 3 解释: 最长的斐波那契式子序列有[1,11,12][3,11,14] 以及 [7,11,18]本题只要求长度不要求输出具体序列因此即使存在多个长度为 3 的候选答案也只需返回3。前置知识动态规划原文档将本题归类为动态规划DP专题本仓库的 thinkings/dynamic-programming.md 系统梳理了动态规划的两个核心概念它们是理解本题思路的基础最优子结构如果问题的最优解所包含的子问题的解也是最优的就称该问题具有最优子结构性质。它决定了具体如何解决问题无后效性子问题的解一旦确定就不再改变不受其后更大问题的求解决策影响。它决定了是否可以使用动态规划来解决。此外动态规划的三个要素是状态定义用f(n)等函数描述问题、状态转移方程s[k] choice(s[k]) - s[k1]的阶段间转移关系、枚举状态一维状态用一层循环、二维状态用两层循环且保证不重不漏。原文档特别说明「和一般的 DP 不同这道题是已知状态转移方程。所以我勉强也归类到 DP 吧。」也就是说本题的特殊之处在于转移规则由斐波那契性质直接给出下一项 前两项之和真正需要设计的只是如何高效地枚举起点并验证延伸。核心思路枚举两两起点 集合延伸思路推导题目给出的斐波那契性质本身就是最天然的状态转移规则只要确定了一个序列的前两个元素 a 和 b那么第三项、第四项……就都被唯一决定了a, b - a b - a 2b - 2a 3b - ...因此解题思路可以拆成三步两两枚举数组中的数字作为斐波那契序列的起点 a 和 b注意 a 必须在 b 之前保证子序列顺序延伸验证斐波那契数列的下一项是a b题目给出的信息如果a b不在数组中直接终止本轮延伸继续枚举下一组起点如果a b在数组中说明找到了一个长度为 3 的斐波那契子序列继续尝试扩展到长度 4、5……记录最大长度整个枚举过程记录最大长度并返回若最大值小于 3 则返回 0。复杂度预估枚举两两组合需要O(n²)的时间复杂度对于每次枚举都需要不断检查a b是否在数组中直到不再数组中为止。最坏情况是始终在数组中此时延伸步数约为数组中最大值与最小值之差的对数即log(m1 - m2)其中m1为数组最大值m2为数组最小值。这个对数级别的延伸次数来源于斐波那契数列的指数增长速度值域上限为10^9而斐波那契数列增长极快约每 5 项翻 10 倍因此在值域内能延伸的项数非常有限。关键点用集合实现 O(1) 查表本解法的核心优化在于使用集合Set存储数组中的所有数然后枚举数组中的两两组合并在集合中不断延伸斐波那契数列。如果不使用集合每次判断a b是否在数组中需要遍历数组会导致总复杂度退化到接近O(n³)。而 Python 的set基于哈希表实现单次成员判断的时间复杂度为 O(1)从而把「延伸验证」这一步的开销压到最低这是整个算法能够以O(n²log(m1-m2))运行的基石。代码实现Python3原文档给出了完整的 Python3 实现这里在保留原逻辑的基础上补充注释便于逐行理解class Solution: def lenLongestFibSubseq(self, A: List[int]) - int: s set(A) # 关键点用集合存储所有数实现 O(1) 的成员查询 ans 0 # 记录全局最长的斐波那契式子序列长度 for i in range(len(A)): # 枚举第一个元素 A[i] for j in range(i 1, len(A)): # 枚举第二个元素 A[j]必须排在 i 之后 a, b A[j], A[i] A[j] # a 为当前序列最后一项b 为下一项 t 2 # 当前序列已有 a前两项之一和它的下一项 b while b in s: # 若下一项存在于数组中继续延伸 a, b b, a b # 序列整体后移一项 t 1 # 长度 1 ans max(ans, t) # 更新全局最大长度 return 0 if ans 3 else ans # 长度不足 3 说明不存在返回 0对代码的几点说明起点顺序保证内层循环从i 1开始天然保证了A[i]出现在A[j]之前符合子序列对顺序的要求延伸终止条件while b in s一旦遇到不在数组中的值立即停止避免无意义的空转结果判定斐波那契式子序列要求n 3因此当最大长度小于 3 时返回0这与题目描述完全一致类型标注List[int]需要从typing导入如from typing import List在线评测环境通常已预置。复杂度分析令n为数组长度m1为数组最大值m2为数组最小值时间复杂度O(n²log(m1-m2))。外层两重循环负责枚举两两组合O(n²)内层while循环负责延伸每次延伸查询集合 O(1)延伸次数上界为log(m1 - m2)空间复杂度O(n)。集合s存储了数组的全部 n 个元素。题目的提示还特别注明对于 Java、C、C 以及 C# 的提交时间限制被减少了 50%说明本题对常数因子较为敏感选用集合做哈希查询是实现层面的关键。扩展时间复杂度更优的哈希索引解法原文档指出「这道题还有时间复杂度更好的做法」即把时间复杂度进一步优化到O(n²)。其核心思想是把「两两枚举 集合延伸」改为二维动态规划 值到索引的哈希映射状态定义设dp[j][k]表示以A[j]、A[k]j k作为最后两项的斐波那契式子序列的最大长度状态转移若A[k] - A[j]即前一项存在于数组中且其索引i j则dp[j][k] dp[i][j] 1其中dp[i][j]是以A[i]、A[j]结尾的最长斐波那契式子序列长度初始条件任何两项都可以构成长度为 2 的「种子」即dp[j][k] 2哈希加速预先建立「数值 - 索引」的字典使A[k] - A[j]的查找达到 O(1)从而整体复杂度为O(n²)。这种方法不再依赖值域上的对数延伸步数而是把问题完全转化为二维 DP配合哈希表将单次转移降为 O(1)。它与 thinkings/dynamic-programming.md 中「两个序列的 DP 通常定义dp[i][j]表示以 i、j 结尾的状态」的套路一脉相承可以作为掌握二维状态定义的良好练习。小结LeetCode 873「最长的斐波那契子序列的长度」是一道「转移方程已知、枚举是难点」的动态规划题其价值体现在三个层面思路层面只要确定前两项整个斐波那契式序列就被唯一锁定这启发我们善于利用题目给出的递推性质压缩状态工程层面用哈希集合把「值是否存在」的查询从 O(n) 降到 O(1)是许多序列延伸类题目的通用优化手段进阶层面从「集合枚举」到「二维 DP 哈希索引」展示了同一道题在时间复杂度上的优化路径。本题在仓库中的完整题解位于 problems/873.length-of-longest-fibonacci-subsequence.md并收录于仓库的题目索引 README.md 与 SUMMARY.md 中。若希望进一步夯实动态规划功底可继续研读仓库的 thinkings/dynamic-programming.md其中对最优子结构、无后效性、状态转移方程与状态枚举方式有系统而深入的讲解。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考