中文题目
如果序列 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
注意：本题与主站 873 题相同： https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/
通过代码
高赞题解
动态规划 + 哈希表
从左往右扫描数组内的每一个数字，该数字可能和前面的不同的数字组成不同的斐波那契数列，如在数组 [1,2,3,4,5,6,7,8] 中数字 6 可以组成 2, 5, 6 和 2, 4, 6 两个斐波那契数列。也就是说，解决该问题需要若干步，每一步都面临若干选择，最后需要返回斐波那契数列的长度最大值，所以该问题可以用动态规划解决。
若当前扫描到数字 A[i]，那么 A[i] 前的数字 A[j] (j < i) 都可能与 A[i] 组成斐波那契数列，前提是存在 k < j 使得 A[i] = A[j] + A[k] 成立。这个以 A[i] 结尾前一个数字是 A[j] 的斐波那契数列，是在以 A[j] 结尾前一个数字是 A[k] 的斐波那契数列的基础上增加一个数字 A[i]，因此前者的长度是后者的长度加 1。
可以发现 A[i] 与 A[j] 密切相关，因此可以定义状态转移方程为 f(i, j) 表示以 A[i] 结尾前一个数字是 A[j] 的斐波那契数列长度。如果存在一个数字 k，使得 A[i] = A[j] + A[k] （0 <= k < j < i) 成立，那么 f(i, j) = f(j, k) + 1。若不存在这样的 k 那么 f(i, j) = 2，因为此时虽然 A[i] 和 A[j] 两个数字还不能形成有效的斐波那契数列，但是可能在之后增加一个新的数字就会形成斐波那契数列。
因为状态转移方程有两个参数，因此需要使用二维数组来保存，i 对应二维数组的行号，j 对应二维数组的列号。因为 j < i，所以只会使用二维数组的一半。如果数组的长度为 n，那么 i 的取值为 1 ~ n - 1，j 的取值为 1 ~ i。根据是否存在 k 使得 A[i] = A[j] + A[k] (0 <= k < j < i) 的情况，状态方程可以写成
因为需要查询 A[k] = A[i] - A[j] 是否存在，并且需要得到下标 k，所以需要一个哈希表将数组内所有的数字和下标保存下来供查询。完整的代码如下，时间复杂为 O(n^2)，空间复杂为 O(n^2)。
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
vector<vector<int>> dp(arr.size(), vector<int>(arr.size()));
unordered_map<int, int> mp;
for (int i = 0; i < arr.size(); ++i) {
mp[arr[i]] = i;
}
int ret = 0;
for (int i = 1; i < arr.size(); ++i) {
for (int j = 0; j < i; ++j) {
int temp = arr[i] - arr[j];
// 存在 k 使得 A[i] = A[j] + A[k] (0 <= k < j < i)
if (mp.count(temp) && mp[temp] < j) {
dp[i][j] = dp[j][mp[temp]] + 1;
}
// 不存在 k 使得 A[i] = A[j] + A[k] (0 <= k < j < i)
else {
dp[i][j] = 2;
}
ret = max(ret, dp[i][j]);
}
}
return ret > 2 ? ret : 0;
}
};动态规划 + 二分查找
其实也可以不使用哈希表处理，因为原数组是递增的，可以使用二分查找确定在下标区间 0 ~ j - 1 内是否存在 k 使得 A[k] = A[i] - A[j] 成立。完整代码如下，时间复杂为 O(n^2 logn)，空间复杂为 O(n^2)。
class Solution {
private:
int search(vector<int>& nums, int right, int target) {
int left = 0;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
}
nums[mid] > target ? right = mid - 1 : left = mid + 1;
}
return -1;
}
public:
int lenLongestFibSubseq(vector<int>& arr) {
vector<vector<int>> dp(arr.size(), vector<int>(arr.size()));
int ret = 0;
for (int i = 1; i < arr.size(); ++i) {
for (int j = 0; j < i; ++j) {
int index = search(arr, j - 1, arr[i] - arr[j]);
dp[i][j] = (index != -1) ? dp[j][index] + 1 : 2;
ret = max(ret, dp[i][j]);
}
}
return ret > 2 ? ret : 0;
}
};统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 2318 | 4048 | 57.3% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
