LeetCode 873. 最长的斐波那契子序列的长度
目录
题目描述
题意分析
给一个严格递增的正整数数组
arr，要在它的子序列（可以不连续，但必须保持原有先后顺序）里找出最长的一段，使得从第三项起每一项都等于前两项之和，返回这个最长长度；一个都不存在时返回 0。
题面对「斐波那契式」的定义要求长度至少为 3，这一条不能忽略：任意两个元素都平凡地构成一个长度为 2 的「序列」，如果不设下限，答案恒为 2。所以最后必须有一道
< 3 则返回 0的关卡。
「严格递增」是本题最重的信号，它同时给出三件事。其一，元素互不相同，值到下标的映射是一一对应的，可以用哈希表 $O(1)$ 反查。其二，序列一旦定下前两项，后面每一项都被唯一确定（下一项必须恰好等于前两项之和，而这个值在数组里最多出现一次），也就是说整条序列由它的头两项完全决定。其三，因为元素为正且递增，合法序列内部也必然递增，可以据此剪掉大量不可能的组合。
由「一对元素决定一切」可以反推状态该怎么设计：单个下标不足以刻画一个部分构造好的序列，必须用一对相邻下标。这也解释了为什么复杂度会落在 $O(n^2)$ 而不是 $O(n)$。约束里 $n \le 1000$，$n^2$ 是百万级，完全够用。
边界要盯住：数组长度可能小于 3，此时直接无解；
arr[i] - arr[j]可能等于arr[j]本身（比如2, 4需要前驱 2，但 2 就是arr[j]自己），这种自引用不合法；前驱值可能根本不在数组里，也可能在数组里但位置不在j左边。
解法：两数结尾动态规划
核心思路
枚举起始两项再一路查找后继虽然能做，但不同起点会重复计算相同的链尾。更稳定的面试解法是二维 DP：斐波那契关系需要知道最后两项，单个下标不足以描述状态。
定义
dp[j][i]：以arr[j]、arr[i]为最后两项的最长斐波那契式子序列长度，其中j < i。任意一对元素先视为长度 2，作为后续递推的起点。
最后两项确定后，倒数第三项只能是
prev = arr[i] - arr[j]。利用数组严格递增且元素互异的条件，用哈希表查出prev的唯一位置k：
- 若
k < j，三个下标满足k < j < i，转移为dp[j][i] = dp[k][j] + 1；- 否则当前二元组不能向前接，保持
dp[j][i] = 2。
k < j既保证子序列的下标顺序，也排除了prev == arr[j]的自引用。只判断值存在并不够。
外层按右端点
i递增。计算dp[j][i]时依赖的dp[k][j]早在右端点为j时完成，这是填表不变量。答案只在合法转移发生时更新，因此它要么为 0，要么至少为 3。
解题步骤
- 扫描数组，建立「值 → 下标」哈希表。
- 枚举右端点
i，再枚举0 <= j < i，先令dp[j][i] = 2。- 计算唯一前驱值
prev = arr[i] - arr[j]，在哈希表中查位置k。- 仅当
k < j时，用dp[k][j] + 1更新当前状态和全局答案。- 返回答案；从未出现合法三元组时，答案仍为 0。
以
arr = [1, 2, 3, 4, 5, 6, 7, 8]为例：
dp[1][2] = dp[0][1] + 1 = 3，得到1, 2, 3；dp[2][4] = dp[1][2] + 1 = 4，接成1, 2, 3, 5；dp[4][7] = dp[2][4] + 1 = 5，最终得到1, 2, 3, 5, 8。反例状态
j = 0, i = 1的前驱值也是 1，但其下标k = 0不满足k < j，所以不能把当前元素重复使用。
代码实现
import java.util.HashMap;
class Solution {
public int lenLongestFibSubseq(int[] arr) {
int n = arr.length;
HashMap<Integer, Integer> index = new HashMap<>();
for (int i = 0; i < n; i++) {
index.put(arr[i], i);
}
int[][] dp = new int[n][n];
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
dp[j][i] = 2;
int prev = arr[i] - arr[j];
Integer k = index.get(prev);
if (k != null && k < j) {
dp[j][i] = dp[k][j] + 1;
ans = Math.max(ans, dp[j][i]);
}
}
}
return ans;
}
}
func lenLongestFibSubseq(arr []int) int {
n := len(arr)
index := make(map[int]int)
for i, num := range arr {
index[num] = i
}
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
}
ans := 0
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
dp[j][i] = 2
prev := arr[i] - arr[j]
if k, ok := index[prev]; ok && k < j {
dp[j][i] = dp[k][j] + 1
if dp[j][i] > ans {
ans = dp[j][i]
}
}
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n^2)$。枚举所有有序下标对，每个状态只做一次均摊 $O(1)$ 的哈希查询。
- 空间复杂度：$O(n^2)$。二维 DP 表占主导，索引表另占 $O(n)$。依赖
dp[k][j]会随机落在更早的任意状态上，不能按相邻行简单滚动。
关键点总结
- 状态必须保留最后两项，因为它们共同决定唯一的前驱值。
- 严格递增保证元素互异，才能用一个哈希表完成「值 → 唯一下标」映射。
dp[j][i] = 2是递推基线，不代表长度 2 是合法答案；答案只在成功接入第三项后更新。- 哈希命中后仍要验证
k < j，值关系不能替代子序列的下标顺序。
易错点总结
- 漏掉
k < j：如[1, 2, 4, 5]中，处理末尾(2, 4)时前驱仍是 2；它就是同一个元素，不能重复使用。- 状态初值不是 2：
dp[k][j]会从 0 开始，所有真实长度都少 2。例如[1, 2, 3, 5]会算不出长度 4。- 循环顺序与依赖冲突：计算
dp[j][i]前必须已经完成dp[k][j]，因此要按第二个下标递增填表。- 把所有二元组计入答案：无合法序列时会错误返回 2；只在找到合法前驱后更新
ans，即可自然保留 0。- 按值域开桶：元素上界可达 $10^9$，应使用哈希表，不能创建同值域大小的数组。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1027. 最长等差数列 | 中等 | 状态同为「一对下标」，但公差可由差值直接编码进哈希表，省掉一维 |
| 446. 等差数列划分 II - 子序列 | 困难 | 统计方案数而非最长长度，公差范围极大只能用哈希表存状态，还要处理弱等差项 |
| 300. 最长递增子序列 | 中等 | 下一项不被唯一确定，状态只需一个下标，且可用贪心加二分优化到 $O(n \log n)$ |
| 1218. 最长定差子序列 | 中等 | 公差已给定，前驱值唯一，状态退化成一维哈希表，一趟扫描即可 |
| 368. 最大整除子集 | 中等 | 排序后转移条件改为整除关系，还需回溯还原具体子集而非只报长度 |
| 673. 最长递增子序列的个数 | 中等 | 在 300 的基础上多维护一个计数数组，长度相等时要累加方案数 |
| 1048. 最长字符串链 | 中等 | 前驱由「删一个字符」生成，可枚举出所有候选前驱后查哈希表，思路与本题同源 |
| 594. 最长和谐子序列 | 简单 | 只要求最大最小值相差 1，不要求保持顺序，计数即可，无需 DP |
| LCR 093. 最长的斐波那契子序列的长度 | 中等 | 与本题同题，可直接套用两数结尾的状态定义 |