从Leetcode 每日一题练习继续讨论：
873. 最长的斐波那契子序列的长度
873. Length of Longest Fibonacci Subsequence
题解
本题考虑arr数组的长度最大为1000，则可直接暴力求解，因为在遍历时只要知道了前两个数字实际上就等于知道了整个序列，则从头开始遍历数组，选定了首个数字后，再从剩余数组中遍历选定第二个数字，选定第二个数字后即可不断向后计算序列的下一个数字，使用哈希表判断序列的下一个数组在不在数组中即可，如果不在数组中时，将当前已经得到的序列的长度和保存的最大长度比较并更新最大长度。
代码
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size();
if (n < 3) {
return 0;
}
unordered_map<int, int> num_to_index;
for (int i = 0; i < n; ++i) {
num_to_index[arr[i]] = i;
}
int max_len = 0;
for (int i = 0; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
int first = arr[i];
int second = arr[j];
int current_len = 2;
while (true) {
int next_num = first + second;
if (num_to_index.count(next_num)) {
current_len++;
first = second;
second = next_num;
} else {
break;
}
}
max_len = max(max_len, current_len > 2 ? current_len : 0);
}
}
return max_len;
}
};
