友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
873. 最长的斐波那契子序列的长度
如果序列 X1, X2, …, Xn 满足下列条件，就说它是 斐波那契式 的：
-
n >= 3 -
对于所有
i + 2 <= n，都有Xi + Xi+1 = Xi+2
给定一个严格递增的正整数数组形成序列 arr，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
示例 1：
输入: arr = [1,2,3,4,5,6,7,8] 输出: 5 解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
示例 2：
输入: arr = [1,3,7,11,12,14,18] 输出: 3 解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
提示：
-
3 <= arr.length <= 1000 -
1 <= arr[i] < arr[i + 1] <= 109
思路分析
哈希！遍历数组，模拟斐波那契数列的计算过程。
最优解是使用动态规划。回头尝试一下。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-08-19 21:27:11
*/
public int lenLongestFibSubseq(int[] arr) {
Set<Integer> set = new HashSet<>();
for (int num : arr) {
set.add(num);
}
int result = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
int a = arr[i];
int b = arr[j];
int len = 0;
if (arr[arr.length - 1] < (a + b)) {
break;
}
while (set.contains(a + b)) {
len++;
int temp = a + b;
System.out.println(a + " + " + b + " = " + temp);
a = b;
b = temp;
}
if (len > 0) {
result = Math.max(result, len + 2);
}
}
}
return result;
}