最长的斐波那契子序列的长度

难度: Medium

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

n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+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] <= 10^9

Submission

运行时间: 211 ms

内存: 16.5 MB

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        dic = dict()
        for num in arr:
            dic[num] = 1
        ans = 0
        for i in range(1,n):
            for j in range(i):
                cnt = 2
                a,b = arr[j],arr[i]
                while a + b in dic:
                    c = a + b
                    a = b
                    b = c 
                    cnt += 1
                if cnt > 2: ans = max(ans,cnt)
        return ans

Explain

该题解的主要思路是通过双层循环枚举所有可能的斐波那契序列的前两个元素，然后使用散列表来快速查找序列中的下一个元素。首先，使用一个字典将数组中的所有数字存储起来，用于后续的快速查找。对于数组中的每一对元素 (arr[j], arr[i])，将其视为可能的斐波那契序列的前两个数，然后尝试构建斐波那契序列并计算其长度。如果序列长度大于2，则更新最大长度。这种方法直接根据斐波那契序列的定义，不断查找和更新可能的序列长度，直到无法继续构建为止。

时间复杂度: O(n^2)

空间复杂度: O(n)

# 这段代码实现了寻找最长斐波那契子序列的长度的功能

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)  # 数组的长度
        dic = dict()  # 用于快速查找元素是否存在于数组中
        for num in arr:  # 将数组元素存入字典
            dic[num] = 1
        ans = 0  # 初始化最长长度为0
        for i in range(1,n):  # 从第二个元素开始遍历
            for j in range(i):  # 遍历当前元素前面的所有元素
                cnt = 2  # 初始化当前斐波那契序列的长度
                a,b = arr[j],arr[i]  # 初始化斐波那契序列的前两个数
                while a + b in dic:  # 当序列中下一个斐波那契数存在时
                    c = a + b  # 计算下一个斐波那契数
                    a = b  # 更新序列的前一个数
                    b = c  # 更新序列的当前数
                    cnt += 1  # 序列长度加1
                if cnt > 2: ans = max(ans,cnt)  # 更新最长斐波那契序列的长度
        return ans  # 返回最长斐波那契序列的长度

Explore

在寻找最长斐波那契子序列的过程中，每个斐波那契序列至少需要两个元素作为起始点，即序列的前两个数。从第二个元素开始遍历是为了确保可以选择这两个起始元素。第一个元素前面没有其他元素，因此如果从第一个元素开始，我们无法形成至少包含两个元素的斐波那契式序列。从第二个元素开始可以确保每次迭代都有可能选取一对元素作为斐波那契序列的起始两个数。

在算法实现中，字典被用作快速查找表来判断序列中的某个数字是否存在于原始数组中。每个数组元素作为键，其存在性（标记为1）作为值存入字典。这样，在构建斐波那契序列时，可以在O(1)时间复杂度内直接通过字典查找判断下一个斐波那契数是否存在，而不需要进行线性搜索，从而大幅提高了查找效率和整体算法的性能。

该算法只专注于当前枚举的两个元素作为斐波那契序列的起始点，并基于这两个点尝试构建和延伸序列。对于每一对可能的起始元素，算法计算以它们为开头的斐波那契序列的最大长度。虽然算法确实枚举了所有可能的起始点对，但它并不会在同一时间内考虑多个不同起点的序列组合。因此，每次更新序列长度时，只考虑了从当前选定的起始点扩展出去的序列。