LeetCode 873. 最长的斐波那契子序列的长度 题目详解
2024-08-28 15:00:41
题目详情
如果序列 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 <= 10001 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9- （对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）
题目解析
AC代码
class Solution {
public:
int lenLongestFibSubseq(vector<int>& A) {
int len = A.size();
unordered_map<int,int> dict;
for(int i=0;i<len;i++){
dict[A[i]] = i;
}
vector<vector<int>> store(len,vector<int>(len,2));
int ans = 0;
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
int sum = A[i] + A[j];
if(dict.find(sum)!=dict.end()){
store[j][dict[sum]] = store[i][j] + 1;
if(store[j][dict[sum]] > ans){
ans = store[j][dict[sum]];
}
}
}
}
return ans;
}
};
最新文章
- Hibernate缓存（转）
- 给JavaScript初学者的24条最佳实践(share)
- 获取屏幕分辨率（C#）
- C++中的const关键字的用法
- HTML+CSS学习笔记 (14) - 单位和值
- 一张图看懂开源许可协议，开源许可证GPL、BSD、MIT、Mozilla、Apache和LGPL的区别
- zTree实现单独选中根节点中第一个节点
- 神奇的namespace使用
- GetFontResourceInfo 函数: 获取字体文件对应的字体名
- 前端——JavaScript
- TensorFlow从入门到理解（四）：你的第一个循环神经网络RNN（分类例子）
- VB 批量重命名文件
- 邪恶力量第一至九季/全集Supernatural迅雷下载
- (转) s-video vs. composite video vs. component video 几种视频格式详细说明和比较
- Android中Parcel的分析以及使用
- spark2.4+elasticsearch６.1.1搭建一个推荐系统
- 进制A~Z，全字母26进制转化
- ERROR 1093 (HY000): You can't specify target table 'test' for update in FROM clause
- poj 1080 ——Human Gene Functions——————【最长公共子序列变型题】
- luogu4566 [Vani有约会]雨天的尾巴