Leetcode 873 Length of Longest Fibonacci Subsequence

发表于 |

A sequence X_1, X_2, …, X_n is fibonacci-like if:
· n >= 3
· X_i + X_{i+1} = X_{i+2} for all i + 2 <= n
Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.
(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)

Example 1:
Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:
Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].

Note:

  1. 3 <= A.length <= 1000
  2. 1 <= A[0] < A[1] < … < A[A.length - 1] <= 10^9
    (The time limit has been reduced by 50% for submissions in Java, C, and C++.)

分析：

  1. 对于这种找子串的问题，大家应该敏感一点，虽然不说绝对，但是极大可能是dp，在这里写一下我分析这道题的心路历程
  2. 第一反应，dp[i]表示nums[:i]的最长fiboc序列长度。但仔细想想dp[i]只记录长度，我根本没法去判断nums[i]能否组出一个更长的序列，那用dp[i]记录下一个期望的数（序列中最后两个数的和）？但是就想example2一样，首先可能会有很多期望的值，其次，可能最后最长的那个序列在最初分析数组前几个数时根本不包括其中，所以这个方法应该是行不通。
  3. 第二反应，发现A的长度不超过1000，这不是暗示我n^2的方法嘛，一想dp[i][j]表示nums[i:j]的最长fibco序列长度，乍一看好像可行诶，首先可以初始化，因为j-i<2则dp[i][j] = 0，所有的j-i=2都可以判断出来（因为就三个数），对于j-i>2，可以依次分析dp[i][i+2],dp[i][i+3]…dp[i][j-1]与nums[j]能否构成更长的序列，取最长的那个保存，但想到这里的时候，发现这个方法复杂度好像有点高哦，达到n^3了，想了一会也没想到怎么优化，而且也还是会面临第2点中说的第一个问题，遂放弃。
  4. 第三反应，逆向思维一下，像上面两个方法都是判断最后一个数能不能和前面的组成更长的序列，那为什么不固定住最后的序列，去找前面的序列呢(这个思维正好把第2点中提到的那个“其次”解决了)，dp[i][j]表示以nums[i]和nums[j]结尾的fibco序列的最长长度，则dp[i][j] = dp[nums[j]-nums[i]的index][i] + 1，当然这必须要满足nums[j]-nums[i]在A中

思路：

  1. 用一个字典保存值和下标的对应关系，用于获得nums[j]-nums[i]的index
  2. 集合记录A（有序）中元素，判断nums[j]-nums[i]是否在A中
  3. 这一点inspired by @lee215，判断nums[j]-nums[i] < nums[i] and nums[j]-nums[i] in s，可以避免重复计算
  4. inspired by @lee215，可以用值来代替下标(python版本，它的C++版本是用的我上面说的思路，这么一看python实在太方便了)，可以让代码简洁很多（这是真的大神！！！）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def lenLongestFibSubseq(A):
    dp = collections.defaultdict(int)
    s = set(A)
    res = 0
    for j in xrange(len(A)):
        for i in xrange(j):
            if A[j] - A[i] < A[i] and A[j] - A[i] in s:
                dp[A[i], A[j]] = dp.get((A[j] - A[i], A[i]), 2) + 1
                res = max(res, dp[A[i], A[j]])
    return max(dp.values() or [0])

33 / 33 test cases passed.
diffculty: medium
Runtime: 328 ms