实现findFibonacci函数，在一堆正整数中，找到最长的一组斐波那契数列段

Question

javascript 编程题

// 实现findFibonacci函数，在一堆正整数中，找到最长的一组斐波那契数列段
// 斐波那契数列：一个递增的正整数数列，从第三位起，每个数字都是前两位数字之和，不一定要从 1 开始
// 入参格式参考：
const inputArr = [13, 9, 3, 8, 5, 25, 31, 11, 21];

// 出参格式参考：
//const sequence = [3, 5, 8, 13, 21];

网上大部分的方法，都是找到最长的number，没有返回完整的lists;
完整lists的函数要怎么写吗

Answer 1

一个直观解答，应该不是最优，时间复杂度太高了，超过了O(n ^ 2)。
返回值未处理长度不足3的情况：

function findFibnacci(list) {
    const map = {}, results = []
    for (let num1 of list) {
        map[num1] = true
        for (let num2 of list) {
            if (num2 > num1) {
                results.push([num1, num2])
            }
        }
    }
    let longest = []
    while (results.length) {
        for (let i = results.length - 1; i >= 0; i--) {
            let result = results[i]
            let n1 = result[result.length - 2]
            let n2 = result[result.length - 1]
            let next = n1 + n2
            if (!map[next]) {
                if (result.length > longest.length) {
                    longest = result
                }
                results.splice(i, 1)
                continue
            }
            result.push(next)
        }
    }
    return longest
}

let res = findFibnacci([13, 9, 3, 8, 5, 25, 31, 11, 21])
console.log(res)