# 0873. 最长的斐波那契子序列的长度

### 题目地址(873. 最长的斐波那契子序列的长度)

<https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/>

### 题目描述

```
如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。

（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

 

示例 1：

输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为：[1,2,3,5,8] 。


示例 2：

输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 。


 

提示：

3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
（对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）
```

### 前置知识

* 动态规划

### 公司

* 暂无

### 思路

和一般的 DP 不同，这道题是已知状态转移方程。所以我勉强也归类到 DP 吧。

这道题的思路是两两枚举数组中的数字，不妨称其为 a 和 b。接下来，我们以 a 和 b 为斐波那契的起点， 很明显斐波那契数列的下一个数字应该是 a + b，这是题目给出的信息。

* 如果 a + b 不在数组中，直接终止，继续枚举下一个。
* 如果 a + b 在数组中，说明我们找到了一个长度为 3 的斐波那契子数列。那么继续尝试扩展斐波那契数列长度到 4。。。

上面的枚举需要 $O(n^2)$的时间复杂度，枚举过程记录最大长度并返回即可。

对于每次枚举，我们都需要不断重复检查 a + b 是否在数组中，直到不再数组中为止。因此最坏的情况是一直在数组中，这个时间复杂度大概是数组中最大值和最小值的差值的对数。用公式表示就是 $log(m1 - m2)$，其中 m1 为数组 最大值， m2 为数组最小值。

### 关键点

* 使用集合存储数组中的所有数，然后枚举数组中的两两组合并，去集合中不断延伸斐波那契数列

### 代码

* 语言支持：Python3

Python3 Code:

```python

class Solution:
    def lenLongestFibSubseq(self, A: List[int]) -> int:
        s = set(A)
        ans = 0
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                a, b = A[j], A[i] + A[j]
                t = 2
                while b in s:
                    a, b = b, a + b
                    t += 1
                ans = max(ans, t)
        return 0 if ans < 3 else ans

```

**复杂度分析**

令 n 为数组长度, m1 为数组最大值，m2 为数组最小值。

* 时间复杂度：$O(n^2log(m1-m2))$
* 空间复杂度：$O(n)$

### 扩展

这道题还有时间复杂度更好的做法， 感兴趣的可以参考 [力扣官方题解](https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/solution/zui-chang-de-fei-bo-na-qi-zi-xu-lie-de-chang-du-by/)

### 结尾

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/1n3mq5.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/873.length-of-longest-fibonacci-subsequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.