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

链接：873.最长的斐波那契子序列的长度
难度：Medium
标签：数组、哈希表、动态规划
简介：给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

题解 1 - cpp

• 编辑时间：2022-07-11
• 执行用时：480ms
• 内存消耗：11.6MB
• 编程语言：cpp
• 解法介绍：哈希存储后遍历每条最长链路。

class Solution {
   public:
    int lenLongestFibSubseq(vector<int> &arr) {
        unordered_set<int> s;
        for (auto &num : arr) s.insert(num);
        int ans = 0;
        for (int i = 0; i < arr.size(); i++) {
            for (int j = 0; j < i; j++) {
                ans = max(ans, check(s, arr[j], arr[i]) + 2);
            }
        }
        return ans < 3 ? 0 : ans;
    }
    int check(unordered_set<int> &s, int num1, int num2) {
        if (s.count(num1 + num2)) return 1 + check(s, num2, num1 + num2);
        return 0;
    }
};