LeetCode LCR 093. 最长的斐波那契子序列的长度
目录
题目描述
题意分析
给一个严格递增的正整数数组
arr，在其中找一个最长的子序列（元素相对顺序保留，但可以不连续），使它满足斐波那契性质：长度至少为 3，且从第三项起每一项都等于前两项之和。返回这个最长长度；若不存在任何符合条件的子序列，返回 0。
先把「斐波那契式」的关键性质挖出来：整个序列被它的前两项完全决定。一旦定下 $x_1, x_2$，后面的 $x_3 = x_1 + x_2$、$x_4 = x_2 + x_3$ 全部唯一确定，没有任何自由度。这条性质把「找子序列」从一个看似要枚举 $2^n$ 个子集的问题，压缩成了「枚举起始的两项」——只有 $O(n^2)$ 种。
反过来看也一样有用：序列中相邻的任意两项同样能唯一确定它的延续方式，甚至能唯一确定它的前一项（前一项 = 当前项 − 前一项）。所以「最后两项是什么」就是刻画一条斐波那契链的完整状态。这是本题状态设计的出发点。
「严格递增」这条约束价值很大：它保证数组中没有重复值，因此每个数值到下标的映射是单射，可以放心用哈希表按值查下标；它还保证了任意 $x_i + x_j$ 只可能出现在更靠后的位置，链条只会单向延伸，不存在环。
约束
3 ≤ arr.length ≤ 1000，1 ≤ arr[i] < arr[i+1] ≤ 10^9。$n \le 1000$ 明确指向 $O(n^2)$ 级别的算法；元素值上界 $10^9$ 而两数之和最多 $2 \times 10^9$，已经超出int范围，所以不能先算和再去查表，必须用减法arr[i] - arr[j]反查，这个细节是本题隐藏的溢出陷阱。
边界：长度不足 3 的链不算答案，所以无解时返回 0 而不是 2；数组本身可能完全找不到任何三元组，例如
[1, 2, 4, 8]。
解法：动态规划递推
核心思路
暴力做法是枚举前两项，然后顺着链一路查下去看能延伸多远。这个思路方向正确，但每次都从头重新延伸，同一段链会被反复走很多次；更麻烦的是「顺着往后查」需要不断在数组里找
x + y是否存在。
关键观察是把方向反过来：与其向后延伸，不如向前回溯。一条以
arr[j], arr[i]（j < i）结尾的斐波那契链，它的倒数第三项必然是arr[i] - arr[j]。如果这个值存在于数组中且下标k严格小于j，那么当前链就是「以arr[k], arr[j]结尾的链」再接上一项。这就把长链的答案建立在短链之上，形成了标准的递推。
于是状态定义为：
dp[j][i]表示以arr[j]和arr[i]作为最后两项的最长斐波那契式子序列的长度（约定j < i）。这个二维状态正好对应前面说的「最后两项唯一刻画一条链」。
转移方程：设
delta = arr[i] - arr[j]，若delta在数组中的下标k满足k < j，则dp[j][i] = dp[k][j] + 1；否则arr[j], arr[i]只能作为一条链的开头两项，长度是 2。
这里
k < j这个条件必须严格。k == j意味着arr[i] = 2 * arr[j]，倒数第三项和倒数第二项是同一个元素，违反了子序列下标递增；k > j则意味着倒数第三项排在倒数第二项后面，顺序颠倒。两种情况都必须排除。
不变量是：每个
dp[j][i]都等于以这对元素收尾的最长合法链的长度，且它只依赖下标更小的状态dp[k][j]（k < j < i）。因此按i递增、j递增的顺序遍历，被依赖的值一定已经算好。
答案取所有发生过转移的
dp[j][i]的最大值。只有转移成功才说明链长至少为 3，因此answer初值取 0，不参与转移的 2 永远不会被计入，无解时自然返回 0。
解题步骤
- 建立「值 → 下标」的哈希表：因为数组严格递增无重复，映射是单射。有了它，
arr[i] - arr[j]是否存在于数组中就是 $O(1)$ 查询，这是把整体复杂度压到 $O(n^2)$ 的前提。Go 版用mp[v] = i + 1存下标加一，这样查不到时得到零值 0，减一后是 −1，一个k >= 0的判断就同时覆盖了「不存在」和「下标非法」两种情况，避免了额外的ok分支。
- 把所有
dp[j][i]（j < i）初始化为 2：任意两个元素都可以作为一条链的起始两项，这是递推的基准。初值不是 0，否则转移出来的长度会整体少 2。
- 双层遍历所有有序对：外层
i从 0 到n-1，内层j从 0 到i-1。遍历顺序保证了计算dp[j][i]时它依赖的dp[k][j]（下标对更靠前）早已定型。
- 用减法而不是加法查表：
delta = arr[i] - arr[j]。这既是「向前回溯」的直接体现，也规避了arr[j] + arr[i]最大可达 $2 \times 10^9$ 导致的int溢出。
- 严格检查
k < j再转移：查到delta的下标k后必须确认k < j，才执行dp[j][i] = dp[k][j] + 1并更新答案。转移和更新答案写在同一个分支里，保证只有真正形成了长度 ≥ 3 的链才会影响结果。
- 返回
answer：初值 0 天然表达了「不存在合法子序列」。
以
arr = [1, 2, 3, 5, 8]走一遍，n = 5，答案应为 5。
建表：
1→0、2→1、3→2、5→3、8→4。所有dp[j][i]初始为 2，answer = 0。
i = 1（值 2）：j = 0，delta = 2 - 1 = 1，下标k = 0，但k < j = 0不成立，不转移。
i = 2（值 3）：j = 0，delta = 3 - 1 = 2，k = 1，k < 0不成立，跳过。j = 1，delta = 3 - 2 = 1，k = 0 < 1成立，dp[1][2] = dp[0][1] + 1 = 2 + 1 = 3，answer = 3。这条链是1, 2, 3。
i = 3（值 5）：j = 0，delta = 4，表中不存在，跳过。j = 1，delta = 3，k = 2，k < 1不成立，跳过。j = 2，delta = 5 - 3 = 2，k = 1 < 2成立，dp[2][3] = dp[1][2] + 1 = 3 + 1 = 4，answer = 4。链变成1, 2, 3, 5。
i = 4（值 8）：j = 0，delta = 7不存在。j = 1，delta = 6不存在。j = 2，delta = 8 - 3 = 5，k = 3，但k < 2不成立——这正是顺序检查发挥作用的地方，5 排在 3 后面，不能当倒数第三项。j = 3，delta = 8 - 5 = 3，k = 2 < 3成立，dp[3][4] = dp[2][3] + 1 = 4 + 1 = 5，answer = 5。链是完整的1, 2, 3, 5, 8。
返回 5。再用
arr = [1, 2, 4, 8]核对：所有delta要么查不到，要么下标不满足k < j（如i = 2, j = 1时delta = 2，k = 1不小于j = 1），answer始终为 0，正确表达了无解。若把k < j松成k <= j，[1,2,4,8]会把2, 4当成dp[1][2] = dp[1][1] + 1从而误报长度 3。
代码实现
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length;
// 数组严格递增无重复，值到下标是单射。
Map<Integer, Integer> mp = new HashMap<>();
for (int i = 0; i < n; ++i) {
mp.put(arr[i], i);
}
// dp[j][i]：以 arr[j]、arr[i] 结尾的最长斐波那契式子序列长度，基准为 2。
int[][] dp = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
dp[j][i] = 2;
}
}
int answer = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
// 用减法回溯倒数第三项，同时避免 arr[j] + arr[i] 溢出 int。
int delta = arr[i] - arr[j];
if (mp.containsKey(delta)) {
int k = mp.get(delta);
// k < j 必须严格：k == j 会复用同一元素，k > j 则顺序颠倒。
if (k < j) {
dp[j][i] = dp[k][j] + 1;
answer = Math.max(answer, dp[j][i]);
}
}
}
}
// 只有转移成功才更新答案，因此无解时自然返回 0。
return answer;
}
}
func lenLongestFibSubseq(arr []int) int {
n := len(arr)
// 存下标加一，查不到时零值 0 减一得 -1，与非法下标统一处理。
mp := make(map[int]int, n)
for i, v := range arr {
mp[v] = i + 1
}
// dp[j][i]：以 arr[j]、arr[i] 结尾的最长斐波那契式子序列长度，基准为 2。
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
for j := 0; j < i; j++ {
dp[j][i] = 2
}
}
answer := 0
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
// 用减法回溯倒数第三项。
delta := arr[i] - arr[j]
k := mp[delta] - 1
// k >= 0 表示存在，k < j 保证下标严格递增。
if k >= 0 && k < j {
dp[j][i] = dp[k][j] + 1
answer = max(answer, dp[j][i])
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n^2)$，双层循环枚举所有 $n(n-1)/2$ 个下标对，每对做一次哈希查询和常数次比较。建表是 $O(n)$，初始化
dp是 $O(n^2)$，都不改变量级。n = 1000时约 50 万次操作，轻松通过。- 空间复杂度：$O(n^2)$，主要是
n × n的dp表；哈希表占 $O(n)$。由于dp[j][i]依赖的是「第二维为j」的那一列，无法简单地滚动降维，$O(n^2)$ 是这一解法的自然代价。
关键点总结
- 当序列的后续项被前若干项完全决定时，就用「最后几项」作为状态。斐波那契链由相邻两项决定，所以状态是二维的
(j, i)；若递推关系跨三项，状态就要扩到三维。这条判据可以直接迁移到等差、等比子序列一类题目。- 向前回溯比向后延伸更容易写成递推：向后延伸要不断猜「下一项存不存在」，向前回溯只需一次减法加一次查表，且天然满足「大问题依赖小问题」的方向。
- 用减法而非加法查表，同时解决了溢出与依赖方向两个问题。看到值域上界接近
int一半时，就该警惕求和溢出，这是面试里很容易被追问的细节。- 下标条件
k < j要写严格，它同时保证了「不复用同一元素」和「子序列顺序正确」。凡是子序列类 DP，都要把下标的严格递增关系显式检查。- 答案初值与状态基准值要分开设计：状态基准是 2（任意两项都能起头），答案初值是 0（长度不足 3 不算解）。把两者混为一谈，就会在无解时错误地返回 2。
易错点总结
- 条件写成
k <= j：arr = [1,2,4,8]时i = 2, j = 1, delta = 2, k = 1会被接受，误报长度 3，而正确答案是 0。- 漏掉
k < j只判mp中存在：arr = [1,3,4]时i = 2, j = 0, delta = 3, k = 1 > j会被接受，把1, 4接到排在后面的 3 上，产生非法链。dp基准初始化为 0 而不是 2：arr = [1,2,3]会算出dp[1][2] = 0 + 1 = 1，答案变成 1 而不是 3。- 答案初值设成 2：
arr = [1,2,4,8]会返回 2，但题目要求无解时返回 0。- 用
arr[j] + arr[i]正向查表：arr = [1000000000, 1500000000]之类的输入会让和超过int上界变成负数，查表必然失败甚至误命中。- 哈希表在有重复值时覆盖下标：本题数组严格递增所以无碍，但把这套代码套到允许重复的变体上时，后写入的下标会覆盖先前的，导致
k < j判断失真。- Go 里直接用
mp[delta]而不减一：delta不在表中时零值 0 会被当成合法下标 0，arr = [2,4,7]会把不存在的元素当成arr[0]误报成链。- 循环顺序写成外层
j、内层i：arr = [1,2,3,5,8]计算dp[3][4]时它依赖的dp[2][3]还没算好，读到基准值 2，答案偏小。- 状态定义成「以
arr[i]结尾的最长链」一维形式：arr = [1,2,3,5,8]中 3 既可以接在1,2后也可以是新链的一部分，单靠一个下标无法区分前一项是谁，转移根本写不出来。- 枚举前两项后顺着链向后暴力延伸而不做记忆化：
arr为 1000 个元素的稠密斐波那契风格数组时，同一段链被重复走 $O(n)$ 次，整体退化到 $O(n^3)$，容易超时。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 873. 最长的斐波那契子序列的长度 | 中等 | 与本题完全同题，代码可原样提交 |
| 1027. 最长等差数列 | 中等 | 状态同为「最后两项」，但公差固定，可把差值作为一维直接哈希 |
| 300. 最长递增子序列 | 中等 | 只需一维状态即可刻画，可对照理解「几项决定后续」如何影响状态维数 |
| 446. 等差数列划分 II - 子序列 | 困难 | 同为二维下标对状态，但统计的是方案数且要处理弱等差的计数叠加 |
| 673. 最长递增子序列的个数 | 中等 | 在长度 DP 之外再维护一个计数数组，考察双状态同步转移 |
| 509. 斐波那契数 | 简单 | 同一条递推式的直接计算形态，可用来对照体会「性质」与「构造」的区别 |
| 1 . 两数之和 | 简单 | 同样用哈希表把「某个差值是否存在」降到 $O(1)$，是本题查表技巧的原型 |