LeetCode-Length of Longest Fibonacci Subsequence

https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/

这道题是将在一个串中寻找最长递增子串变成了寻找最长斐波那契子串。

首先，可以想到的最简单的是使用三层循环，固定前两个数字a和b，不断迭代寻找后一个数字是否在A中，如果在，就进行斐波那契额迭代，如果不在，就继续找下两个数字的组合。这种算法的复杂度为O(n^3)，比较难以接收。不过可以用空间换时间，使用set将从串中寻找后一个数字的时间减小为O(1)，但是因为还需要不断进行迭代查找后面是否还有符合斐波那契规律的串，又因为斐波那契数字呈指数型增长，所以复杂度是O(n^2logM)，其中，M为A中的最大数字。

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        if(A.size() < 3) return 0;
        set<int> a_set(A.begin(), A.end());
        int result = 0;
        for(int i=0; i<A.size(); ++i) {
            for(int j=0; j<i; ++j) {
                int a = A[j], b = A[i];
                int c = a+b;
                int l = 2;
                while(a_set.find(c) != a_set.end()) {
                    a = b;
                    b = c;
                    c = a+b;
                    ++l;
                }
                result = l>result ? l : result;
            }
        }
        return result>=3 ? result : 0;
    }
};

接下来，还可以用DP去优化上面的解法，使得复杂度降低为O(n^2)。

假设f(i, j)为第以i和j为前两项的斐波那契额数列时，它前面的项数。那么，就可以得到f(i, j) = f(j-i, i) + 1 if j-i>i and j-i in A。

根据公式可以写出以下程序，为了简单，使用i, j和k表示斐波那契数列的连续三项。在程序中，使用k和j进行外层循环，内层计算出i的值。

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        if(A.size() < 3) return 0;
        unordered_map<int,int> a_index;
        vector<vector<int>> a_map(A.size(), vector<int>(A.size(), 2));
        int result = 0;
        for(int i=0; i<A.size(); ++i) {
            a_index.insert(make_pair(A[i], i));
        }
        for(int k=0; k<A.size(); ++k) {
            for(int j=0; j<k; ++j) {
                if(A[k]-A[j]<A[j] && a_index.find(A[k]-A[j]) != a_index.end()) {
                    int i = a_index[A[k]-A[j]];
                    a_map[j][k] = a_map[i][j] + 1;
                    result = a_map[j][k] > result ? a_map[j][k] : result;
                } 
                
            }
        }
        return result>=3 ? result : 0;
    }
};

还可以使用map保存a_map这个稀疏矩阵（几乎全为2），以降低程序的空间复杂度。

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        int l = A.size();
        if(l < 3) return 0;
        unordered_map<int,int> a_index;
        unordered_map<int,int> a_map;
        int result = 0;
        for(int i=0; i<l; ++i) {
            a_index.insert(make_pair(A[i], i));
        }
        for(int k=0; k<l; ++k) {
            for(int j=0; j<k; ++j) {
                if(A[k]-A[j]<A[j] && a_index.find(A[k]-A[j]) != a_index.end()) {
                    int i = a_index[A[k]-A[j]];
                    a_map[j*l+k] = a_map[i*l+j] + 1;
                    result = a_map[j*l+k]+2 > result ? a_map[j*l+k]+2 : result;
                } 
                
            }
        }
        return result>=3 ? result : 0;
    }
};

需要注意的是上面的哈希表都没有排序的需求，所以应该使用unordermap，让map的查询时间复杂度为O(1)。