Medium

题目描述

给你一个正整数数组 nums。

斐波那契数组是一个连续的序列，其第三项及之后的每一项都等于前两项的和。

返回 nums 中最长斐波那契子数组的长度。

注意：长度为 1 或 2 的子数组总是斐波那契数组。

示例 1：

输入：nums = [1,1,1,1,2,3,5,1]
输出：5
解释：
最长的斐波那契子数组是 nums[2..6] = [1, 1, 2, 3, 5]。
[1, 1, 2, 3, 5] 是斐波那契数组，因为 1 + 1 = 2，1 + 2 = 3，2 + 3 = 5。

示例 2：

输入：nums = [5,2,7,9,16]
输出：5
解释：
最长的斐波那契子数组是 nums[0..4] = [5, 2, 7, 9, 16]。
[5, 2, 7, 9, 16] 是斐波那契数组，因为 5 + 2 = 7，2 + 7 = 9，7 + 9 = 16。

示例 3：

输入：nums = [1000000000,1000000000,1000000000]
输出：2
解释：
最长的斐波那契子数组是 nums[1..2] = [1000000000, 1000000000]。
[1000000000, 1000000000] 是斐波那契数组，因为其长度为 2。

约束条件：

  • 3 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

这是一个动态规划问题，核心思想是检查连续的三个数是否满足斐波那契关系。

思路分析：

  1. 基本观察：斐波那契数组要求从第三个元素开始，每个元素都等于前两个元素的和。长度为1或2的数组总是有效的。

  2. 一次遍历解法：我们可以用一次遍历来解决。维护当前斐波那契子数组的长度，初始为2（任意两个相邻元素）。当遍历到第i个元素时：

    • 如果 nums[i] == nums[i-1] + nums[i-2]，说明可以扩展当前的斐波那契序列，长度加1
    • 否则，重新开始一个长度为2的序列

  3. 优化思路：由于题目要求连续子数组，我们不需要考虑所有可能的起始位置组合，只需要贪心地维护当前最长的序列即可。

  4. 边界处理：数组长度至少为3，且长度小于等于2的子数组都是有效的，所以最小返回值是2。

这种方法时间复杂度为O(n)，空间复杂度为O(1)，是最优解法。

代码实现

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return n;
        
        int maxLen = 2;
        int currentLen = 2;
        
        for (int i = 2; i < n; i++) {
            if (nums[i] == nums[i-1] + nums[i-2]) {
                currentLen++;
            } else {
                currentLen = 2;
            }
            maxLen = max(maxLen, currentLen);
        }
        
        return maxLen;
    }
};

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return n
        
        max_len = 2
        current_len = 2
        
        for i in range(2, n):
            if nums[i] == nums[i-1] + nums[i-2]:
                current_len += 1
            else:
                current_len = 2
            max_len = max(max_len, current_len)
        
        return max_len

public class Solution {
    public int LongestSubarray(int[] nums) {
        int n = nums.Length;
        if (n < 3) return n;
        
        int maxLen = 2;
        int currentLen = 2;
        
        for (int i = 2; i < n; i++) {
            if (nums[i] == nums[i-1] + nums[i-2]) {
                currentLen++;
            } else {
                currentLen = 2;
            }
            maxLen = Math.Max(maxLen, currentLen);
        }
        
        return maxLen;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function(nums) {
    const n = nums.length;
    if (n < 3) return n;
    
    let maxLen = 2;
    let currentLen = 2;
    
    for (let i = 2; i < n; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组一次，每个元素访问常数次
空间复杂度O(1)只使用了几个额外的变量，不依赖于输入大小