016-力扣刷题873--最长的斐波那契子序列的长度

如果序列 

$$X_1, X_2, ..., X_n $$
满足下列条件，就说它是 斐波那契式 的：

n >= 3 对于所有$ i + 2 <= n$，都有 X_i + X_{i+1} = X_{i+2} 给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。

（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

示例 1：

输入: [1,2,3,4,5,6,7,8] 输出: 5 解释: 最长的斐波那契式子序列为：[1,2,3,5,8] 。 示例 2：

输入: [1,3,7,11,12,14,18] 输出: 3 解释: 最长的斐波那契式子序列有： [1,11,12]，[3,11,14] 以及 [7,11,18] 。

提示：

3 <= A.length <= 1000 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9 （对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def lenLongestFibSubseq(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        s=set(A)  #set以后是一个集合,去掉重复的元素
        n=len(A) #n是A的长度
        result=0
        #下面开始遍历
     #   [1,2,3,4,5,6,7]#要进行两个for循环进行组合
         # 首选第一个循环取出第一位,第二个循环取出后面的所有的元素 进行不同的组合前两个数 1,2   1,3   1,4   1,5    1,6  2,3    2,4  .....
        #取出前两位后计算后面的结果判断是不是在剩下的元素串中 S
        for i in range(n-1):  #要留出一位给第二个元素
            for j in range(i+1,n): #这里要注意是i+1
                a,b=A[i],A[j] #取出两个元素赋给a,b
                count = 2 #只要是取出两个值说面最少也得有两个数
                #下面开始循环计算判断下面的结果是不是在s中
                while a+b in s: #只要计算出的结果在s中那么继续循环
                    a,b=b,a+b  #继续向下迭代
                    count+=1 #个数加1
                    result =max(count,result) #每次保存的都是结果最大的
        return result if result > 0 else 0   #返回最终的计算结果  这里这么写是因为只有n>=3才能组成序列否则的话就返回0