What is a Fibonacci-like subsequence?

A Fibonacci-like subsequence is a sequence where each element (from the third onward) is the sum of the two preceding elements.

How can I optimize my solution for larger arrays?

Use dynamic programming with hash tables to speed up lookup times and avoid unnecessary computations for larger arrays.

Can this problem be solved without dynamic programming?

While a brute-force approach is possible, dynamic programming is the most efficient method for solving this problem in a reasonable time frame.

Why is a hash table used in this problem?

A hash table is used to quickly check if the sum of two elements exists in the array, optimizing the solution's time complexity.

What is the time complexity of this problem?

The time complexity is O(n^2), where n is the length of the array, due to the nested iteration over pairs of elements.

#873

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

如果序列 x 1 , x 2 , ..., x n 满足下列条件，就说它是斐波那契式的： n >= 3 对于所有 i + 2 ，都有 x i + x i+1 == x i+2 给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果不存在，返回 0…

数组哈希表动态规划

题目描述

如果序列 x₁, x₂, ..., x_n 满足下列条件，就说它是 斐波那契式 的：

n >= 3
对于所有 i + 2 <= n，都有 x_i + x_i+1 == x_i+2

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

子序列 是通过从另一个序列 arr 中删除任意数量的元素（包括删除 0 个元素）得到的，同时不改变剩余元素顺序。例如，[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⁹

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示以 $\textit{arr}[i]$ 作为最后一个元素，以 $\textit{arr}[j]$ 作为倒数第二个元素的最长斐波那契子序列的长度。初始时，对于任意的 $i \in [0, n)$ 和 $j \in [0, i)$ ，都有 $f[i][j] = 2$ 。其余的元素都是 $0$ 。

我们用一个哈希表 $d$ 记录数组 $\textit{arr}$ 中每个元素对应的下标。

然后，我们可以枚举 $\textit{arr}[i]$ 和 $\textit{arr}[j]$ ，其中 $i \in [2, n)$ 且 $j \in [1, i)$ 。假设当前枚举到的元素是 $\textit{arr}[i]$ 和 $\textit{arr}[j]$ ，我们可以得到 $\textit{arr}[i] - \textit{arr}[j]$ ，记作 $t$ 。如果 $t$ 在数组 $\textit{arr}$ 中，且 $t$ 的下标 $k$ 满足 $k < j$ ，那么我们可以得到一个以 $\textit{arr}[j]$ 和 $\textit{arr}[i]$ 作为最后两个元素的斐波那契子序列，其长度为 $f[i][j] = \max(f[i][j], f[j][k] + 1)$ 。我们可以用这种方法不断更新 $f[i][j]$ 的值，然后更新答案。

枚举结束后，返回答案即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是数组 $\textit{arr}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        f = [[0] * n for _ in range(n)]
        d = {x: i for i, x in enumerate(arr)}
        for i in range(n):
            for j in range(i):
                f[i][j] = 2
        ans = 0
        for i in range(2, n):
            for j in range(1, i):
                t = arr[i] - arr[j]
                if t in d and (k := d[t]) < j:
                    f[i][j] = max(f[i][j], f[j][k] + 1)
                    ans = max(ans, f[i][j])
        return ans

speed

复杂度分析

指标	值
时间	O(n^2)
空间	O(n^2)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate leverage dynamic programming efficiently for this problem?
question_mark
Does the candidate recognize the importance of using a hash table for faster lookup?
question_mark
Can the candidate explain the Fibonacci-like structure and how it applies to subsequences?

warning

常见陷阱

外企场景

error
Not considering all pairs of elements, which can miss valid subsequences.
error
Misunderstanding the Fibonacci-like condition, leading to incorrect subsequences.
error
Not optimizing the lookup with a hash table, which increases time complexity unnecessarily.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Variation with unsorted arrays: Can the approach be adjusted to handle non-strictly increasing arrays?
arrow_right_alt
Variation with larger inputs: How would the algorithm scale if the array length increased significantly beyond 1000?
arrow_right_alt
Variation with multiple valid subsequences: How to handle cases where there are multiple Fibonacci-like subsequences with the same length?

help

常见问题

外企场景

继续练习

#823 带因子的二叉树 #792 匹配子序列的单词数 #996 平方数组的数目