Medium

题目描述

如果序列 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] <= 10^9

解题思路

这道题可以使用动态规划来解决。核心思想是以每两个数作为斐波那契数列的前两个数，然后尝试向后扩展。

解法一：哈希表 + 动态规划（推荐）

  1. 使用哈希表记录每个数字的下标位置，便于快速查找
  2. 用 dp[i][j] 表示以 arr[i] 和 arr[j] 为结尾的斐波那契数列的长度（其中 i < j）
  3. 对于每对 (i, j)，查找是否存在 arr[k] = arr[i] + arr[j]，如果存在则更新 dp[j][k]
  4. 状态转移：dp[j][k] = max(dp[j][k], dp[i][j] + 1)

解法二：暴力枚举 对于每对可能的起始数字，不断查找下一个斐波那契数，直到找不到为止。这种方法时间复杂度较高。

第一种方法更加优雅且效率更高，通过动态规划避免了重复计算，是推荐的解法。

时间复杂度为 O(n²)，空间复杂度为 O(n²)，其中 n 是数组长度。

代码实现

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int, int> index;
        
        // 建立数值到索引的映射
        for (int i = 0; i < n; i++) {
            index[arr[i]] = i;
        }
        
        // dp[i][j] 表示以 arr[i] 和 arr[j] 结尾的斐波那契数列长度
        vector<vector<int>> dp(n, vector<int>(n, 0));
        int maxLen = 0;
        
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                int target = arr[j] - arr[i];
                if (target < arr[i] && index.count(target)) {
                    int k = index[target];
                    dp[i][j] = dp[k][i] + 1;
                } else {
                    dp[i][j] = 2;
                }
                maxLen = max(maxLen, dp[i][j]);
            }
        }
        
        return maxLen >= 3 ? maxLen : 0;
    }
};

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        index = {val: i for i, val in enumerate(arr)}
        
        # dp[i][j] 表示以 arr[i] 和 arr[j] 结尾的斐波那契数列长度
        dp = [[0] * n for _ in range(n)]
        max_len = 0
        
        for j in range(1, n):
            for i in range(j):
                target = arr[j] - arr[i]
                if target < arr[i] and target in index:
                    k = index[target]
                    dp[i][j] = dp[k][i] + 1
                else:
                    dp[i][j] = 2
                max_len = max(max_len, dp[i][j])
        
        return max_len if max_len >= 3 else 0

public class Solution {
    public int LenLongestFibSubseq(int[] arr) {
        int n = arr.Length;
        Dictionary<int, int> index = new Dictionary<int, int>();
        
        // 建立数值到索引的映射
        for (int i = 0; i < n; i++) {
            index[arr[i]] = i;
        }
        
        // dp[i][j] 表示以 arr[i] 和 arr[j] 结尾的斐波那契数列长度
        int[,] dp = new int[n, n];
        int maxLen = 0;
        
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                int target = arr[j] - arr[i];
                if (target < arr[i] && index.ContainsKey(target)) {
                    int k = index[target];
                    dp[i, j] = dp[k, i] + 1;
                } else {
                    dp[i, j] = 2;
                }
                maxLen = Math.Max(maxLen, dp[i, j]);
            }
        }
        
        return maxLen >= 3 ? maxLen : 0;
    }
}

/**
 * @param {number[]} arr
 * @return {number}
 */
var lenLongestFibSubseq = function(arr) {
    const n = arr.length;
    const index = new Map();
    
    // 建立数值到索引的映射
    for (let i = 0; i < n; i++) {
        index.set(arr[i], i);
    }
    
    // dp[i][j] 表示以 arr[i] 和 arr[j] 结尾的斐波那契数列长度
    const dp = Array.from({length: n}, () => new Array(n).fill(0));
    let maxLen = 0;
    
    for (let j = 1; j < n; j++) {
        for (let i = 0; i < j; i++) {
            const target = arr[j] - arr[i];
            if (target < arr[i] && index.has(target)) {
                const k = index.get(target);
                dp[i][j] = dp[k][i] + 1;
            } else {
                dp[i][j] = 2;
            }
            maxLen = Math.max(maxLen, dp[i][j]);
        }
    }
    
    return maxLen >= 3 ? maxLen : 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n²)双重循环遍历所有数对，每次操作为O(1)
空间复杂度O(n²)dp数组和哈希表的空间开销

相关题目