题目链接：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/
思路
方法一、二分+枚举
直接想法
题目要求斐波那契数列长度要大于等于3，就等于说要确定 x[1] 和 x[2]来确定x[3]…x[n]之和的数列，所以我们用两层for循环来枚举x[1] 和 x[2] ,因为斐波那契数列满足 x[i] = x[i - 1] + x[i - 2]， 所以x[3] = x[1] + x[2] x[4] = x[3] + x[2]…，我们只需要三个变量来不断变换， 每次从 arr 中找前两个数，然后查看后续在符合斐波那契的数在arr中是否存在
算法
1.第一层 for 循环 来确定第一个数
2.第二层 for 循环 来确定第二个数
3.用 tmpi 记录第一个数，用 tmpj 记录第二个数， 用sum = tmpi + tmpj
4.用二分查找 搜索sum是否存在于 arr 数组
5.tmpi -> tmpj， tmpj -> sum， sum -> sum + tmpj
代码示例
func binarySearch(arr []int, target int, l int, r int) int { //在arr[l...r]中查找target for l <= r { //middleIndex := r+l/2 //注意：这里容易产生bug（r+l溢出int最大值）,改写成如下方式 middleIndex := l + (r-l)/2 if arr[middleIndex] == target { return middleIndex }else if arr[middleIndex] > target { //在arr[l...middleIndex - 1]中查找target r = middleIndex - 1 }else { //在arr[middleIndex + 1...r]中查找target l = middleIndex + 1 } } return -1 } func lenLongestFibSubseq(arr []int) (ans int) { n := len(arr) for i := range arr{ if n - i < ans{ break } for j := i + 1; j < n; j++{ cnt := 2 tmpi := arr[i] tmpj := arr[j] sum := tmpi + tmpj if n - j + 3 < ans{ break } for binarySearch(arr, sum, j + 1, n - 1) >= 0{ cnt++ tmpi, tmpj, sum = tmpj, sum, sum + tmpj } if ans < cnt && cnt >= 3{ ans = cnt } } } return }
复杂度分析
- 时间复杂度：O(n2 * log2n) 其中n是arr数组的长度，用两层for 循环确定前两个数需要O(n2)的时间，用二分去搜索后续斐波那契数列是否存在在数组中需要O(log2n)
- 空间复杂度：O(1) 不需要申请额外空间
方法二、哈希 + 枚举
直接想法
在方法一的基础上，我们发现用二分查找搜索斐波那契数会重复搜索存在的数，虽然顺序遍历节省了很多时间，居然第三层我只需要搜索这个数是否存在，我们可以用更优秀的哈希表来存arr数组里的数，那我们可以省去第三层的搜索时间，只需要O(1)的时间
算法
1.用哈希表map来循环arr数组记录数
2.第一层 for 循环 来确定第一个数
3.第二层 for 循环 来确定第二个数
4.用 tmpi 记录第一个数，用 tmpj 记录第二个数， 用sum = tmpi + tmpj
5.用 哈希表map 搜索sum是否存在于 arr 数组
6.tmpi -> tmpj， tmpj -> sum， sum -> sum + tmpj
func lenLongestFibSubseq(arr []int) (ans int) { mp := map[int]bool{} for i := range arr{ mp[arr[i]] = true } for i := range arr{ if len(arr) - i < ans{ break } for j := i + 1; j < len(arr); j++{ cnt := 2 tmpi := arr[i] tmpj := arr[j] sum := tmpi + tmpj if len(arr) - j + 2 < ans{ break } for mp[sum]{ cnt++ tmpi, tmpj, sum = tmpj, sum, sum + tmpj } if ans < cnt && cnt >= 3{ ans = cnt } } } return }
复杂度分析
- 时间复杂度：O(n2) 其中n是arr数组的长度，用两层for 循环确定前两个数需要O(n2)的时间，用哈希表搜索后续斐波那契数列是否存在在数组中需要O(1)
- 空间复杂度：O(n) 需要申请一个长度n的map哈希表
