LeetCode-873. Length of Longest Fibonacci Subsequence

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: 5Explanation:The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

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

Note:

​​3 <= A.length <= 1000​​​​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++.)

题解：

第一次O(n^3)直接tle

class Solution {public: int lenLongestFibSubseq(vector& A) { int n = A.size(); int maxi = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int len = 0; queue q; q.push(A[i]); q.push(A[j]); for (int k = j + 1; k < n; k++) { if (q.front() + q.back() == A[k]) { q.pop(); q.push(A[k]); if (len == 0) { len = 3; } else { len++; } } } maxi = max(len, maxi); } } return maxi; }};

第二次vector查找仍然tle

class Solution {public: int lenLongestFibSubseq(vector& A) { int n = A.size(); int maxi = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int len = 0; int a = A[i]; int b = A[j]; vector::iterator tmp = find(A.begin(), A.end(), a + b); while(tmp != A.end()) { b = a + b; a = b - a; if (len == 0) { len = 3; } else { len++; } tmp = find(A.begin(), A.end(), a + b); } maxi = max(maxi, len); } } return maxi; }};

只能用map了啊，AC

class Solution {public: int lenLongestFibSubseq(vector& A) { int n = A.size(); map mp; int maxi = 0; for (int i = 0; i < n; i++) { mp.insert(pair(A[i], 1)); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int len = 0; int a = A[i], b = A[j]; while (true) { if (mp.find(a + b) != mp.end()) { b = a + b; a = b - a; if (len == 0) { len = 3; } else { len++; } } else { break; } } maxi = max(maxi, len); } } return maxi; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。