873. 最长的斐波那契子序列的长度

🟠   🔖  数组 哈希表 动态规划  🔗 力扣 LeetCode

题目

A sequence x1, x2, ..., xn is Fibonacci-like if:

• n >= 3
• xi + xi+1 == xi+2 for all i + 2 <= n

Given a strictly increasing array arr of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence ofarr. If one does not exist, return 0.

A subsequence is derived from another sequence arr by deleting any number of elements (including none) from arr, 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: arr = [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: arr = [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].

Constraints:

• 3 <= arr.length <= 1000
• 1 <= arr[i] < arr[i + 1] <= 10^9

题目大意

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

• n >= 3
• 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增 的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

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

示例 1：

输入: arr =[1,2,3,4,5,6,7,8]

输出: 5

解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

示例 2：

输入: arr =[1,3,7,11,12,14,18]

输出: 3

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

提示：

• 3 <= arr.length <= 1000
• 1 <= arr[i] < arr[i + 1] <= 10^9

解题思路

思路一：动态规划 + 双指针

1. 状态定义 我们用 dp[cur][next] 表示以 arr[cur] 和 arr[next] 作为最后两个元素的最长斐波那契式子序列的长度。

2. 状态转移 我们遍历 next 作为子序列的最后一个元素，使用 prev 和 cur 作为前两个元素：

• 如果 arr[prev] + arr[cur] > arr[next]，说明当前 prev 太大了，cur--（向前调整 cur）。
• 如果 arr[prev] + arr[cur] < arr[next]，说明 prev 太小了，prev++（向后调整 prev）。
• 如果 arr[prev] + arr[cur] == arr[next]，说明 arr[prev]、arr[cur]、arr[next] 可以组成斐波那契式子序列：
  • dp[cur][next] = dp[prev][cur] + 1
  • 更新最长子序列的长度 maxLen
  • 继续向前寻找新的 prev 和 cur 组合。

3. 初始状态

• dp[cur][next] 初始值为 0，表示默认没有匹配的斐波那契式子序列。
• maxLen 记录最长的序列长度，初始化为 0。

4. 终止条件

• 遍历完整个数组后，如果 maxLen > 0，说明存在符合要求的序列，返回 maxLen + 2（因为 dp[cur][next] 记录的是额外的长度，需要加上 prev 和 cur）。
• 否则返回 0（表示不存在符合要求的斐波那契子序列）。

复杂度分析

• 时间复杂度：O(n^2)，遍历所有可能的 (prev, cur, next) 组合。
• 空间复杂度：O(n^2)，使用 dp 数组存储状态。

---

思路二：暴力遍历

1. 枚举所有起点 我们尝试所有 arr[i] 和 arr[j] 作为子序列的前两个元素 (prev, cur)，然后查找后续元素是否满足斐波那契关系。

2. 查找后续元素

• 计算 next = prev + cur，判断 next 是否在 arr 中：
  • 如果 next 存在，则更新 prev = cur，cur = next，长度 len++，继续查找。
  • 如果 next 不存在，则停止，记录 maxLen。

3. 终止条件

• 遍历完整个数组后，返回 maxLen 作为最长子序列的长度。

复杂度分析

• 时间复杂度：O(n^2 logM)，其中 M 为 arr 的最大元素，查找操作 while(Set.has()) 近似 O(logM)。
• 空间复杂度：O(n)，使用 Set 存储 arr 中的元素，加速查找。

代码

动态规划 + 双指针

/**
 * @param {number[]} arr
 * @return {number}
 */
var lenLongestFibSubseq = function (arr) {
	const n = arr.length;
	let dp = new Array(n).fill().map(() => new Array(n).fill(0));
	let maxLen = 0;
	for (let next = 2; next < n; next++) {
		let prev = 0;
		let cur = next - 1;
		while (prev < cur) {
			let sum = arr[prev] + arr[cur];
			if (sum > arr[next]) {
				cur--;
			} else if (sum < arr[next]) {
				prev++;
			} else {
				dp[cur][next] = dp[prev][cur] + 1;
				maxLen = Math.max(maxLen, dp[cur][next]);
				cur--;
				prev++;
			}
		}
	}
	return maxLen == 0 ? 0 : maxLen + 2;
};

暴力遍历

/**
 * @param {number[]} arr
 * @return {number}
 */
var lenLongestFibSubseq = function (arr) {
	const n = arr.length;
	let numSet = new Set(arr);
	let maxLen = 0;
	for (let i = 0; i < n; i++) {
		for (let j = i + 1; j < n; j++) {
			let prev = arr[j];
			let cur = arr[i] + arr[j];
			let len = 2;
			while (numSet.has(cur)) {
				len++;
				let temp = cur;
				cur += prev;
				prev = temp;
				maxLen = Math.max(maxLen, len);
			}
		}
	}
	return maxLen;
};

相关题目

题号	标题	题解	标签	难度	力扣
509	斐波那契数	[✓]	递归 记忆化搜索 数学 1+	🟢	🀄️ 🔗