实现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)

Answer 2

不知道对不对，如果有问题还望指教 (#^.^#)

function findeFibonacci(arr) {

var arr1 = arr.sort(function(a, b) {
    return a-b;
})
var tempArr = [];
tempArr.push(arr1[0], arr[1])
for(var i=2; i<arr1.length;i++) {
    if(arr1[i] == arr1[i-2] + arr1[i-1]) {
        tempArr.push(arr1[i])
    } else {
        arr1.splice(i, 1)
        arr1 = arr1
        i--;
    }
}
return tempArr;

}

Answer 3

最近面试遇到了，贴一下实现。
1、主要的思路就是穷举出所有fib，再比较各个fib的大小，从而得到最长。
2、穷举的算法，用了一个三层的for循环，核心是查找以有序数组中各项开头的fib，如：对于[3,5,8,13]，会分别以3、5作为fib的开头，查找得到所有的fib为：[3,5,8,13,],[5,8,13]。

@牛书书 的实现和本实现有一定的差异，比较巧妙。其是先存储了前两位相加的所有可能的数组，再对这个二维数组遍历穷举获得fib。
相对于本实现，其通过对象做key来匹配num1+num2，复杂度要低一些。

function findFibonacci (inputArr) {
  let longest = []

  if (inputArr.length < 3) {
    return longest
  }
  // 1. 对入参排序，并去重
  const list = [...new Set(inputArr)].sort((a,b) => a-b)

  // 2. 穷举得到所有的fibs
  const fibs = []
  for (let i = 0; i < list.length - 2; i++) {
    let firstNum = list[i]
    // 2.1 遍历获取所有以 firstNum 开始的fib
    for (let j = i+1; j < list.length - 1; j++) {
      let tmpFib = []
      let secondNum = list[j]
      for (let k = j+1; k < list.length; k++) {
        let curNum = list[k]
        // tmpFib为空时，需要先初始化一个fab
        if (tmpFib.length === 0) {
          if (curNum === firstNum + secondNum) {
            tmpFib = [firstNum, secondNum, curNum]
          }
        } else {
        // tmpFib已初始化，则查找后续的数
          let num1 = tmpFib[tmpFib.length - 2]
          let num2 = tmpFib[tmpFib.length - 1]
          if (curNum === num1 + num2) {
            tmpFib.push(curNum)
          }
        }
      }
      if (tmpFib.length > 0) {
        fibs.push(tmpFib)
      }
    }
  }
  
  // 2.2 比较得出最长的fib
  fibs.forEach(item => {
    if (item.length > longest.length) {
      longest = item
    }
  })
  console.debug('全部fibs', fibs)
  return longest
}

用例：

const inputArr = [13, 9, 3, 8, 5, 25, 31, 11, 21];
const sequence = [3, 5, 8, 13, 21];
console.group('test1')
console.log('入参', inputArr)
console.log('出参及期望出参', findFibonacci(inputArr), sequence)
console.groupEnd('test1')

const inputArr2 = [3, 5, 8, 11, 19, 21, 30, 35, 49, 13]
const sequence2 = [3,8,11,19,30,49]
console.group('test2')
console.log('入参', inputArr2)
console.log('出参及期望出参', findFibonacci(inputArr2), sequence2)
console.groupEnd('test2')

const inputArr3 = [1, 3, 5, 8, 11, 19, 21, 30, 35, 49, 13, 13, 55, 34]
const sequence3 = [ 3, 5, 8, 13, 21, 34, 55]
console.group('test3')
console.log('入参', inputArr3)
console.log('出参及期望出参', findFibonacci(inputArr3), sequence3)
console.groupEnd('test3')

const inputArr4 = [1, 3]
const sequence4 = []
console.group('test4')
console.log('入参', inputArr4)
console.log('出参及期望出参', findFibonacci(inputArr4), sequence4)
console.groupEnd('test4')