4078. 连续三项斐波那契数之和

难度简单

题目描述

给你一个整数 n。

斐波那契数列 以 0 和 1 开始，之后的每个数都是前两个数之和。它的前几项为 0, 1, 1, 2, 3, 5, 8, 13, ...。

如果 n 可以表示为斐波那契数列中 连续三项之和，则返回 true；否则返回 false。

示例 1：

输入： n = 16

输出： true

解释：

连续三项 3、5 和 8 的和为 3 + 5 + 8 = 16。

示例 2：

输入： n = 8

输出： false

解释：

虽然 1 + 2 + 5 = 8，但这三项在斐波那契数列中并不连续。不存在连续三项的和等于 8。

示例 3：

输入： n = 2

输出： true

解释：

斐波那契数列的前三项之和为 0 + 1 + 1 = 2。

提示：

1 <= n <= 10⁹

解法

方法一：斐波那契数判定

思考

\(n\) 可以到 \(10^9\)，从 \(1\) 累加到 \(n\) 不现实。不超过这个上界的斐波那契数只有几十项，生成之后检查每一组连续三项就已经够用。

连续三项之间还有更紧的关系。由递推，\(F_{i+2}=F_i+F_{i+1}\)，三项之和正好是最后一项的两倍。

问题就变成判断 \(n\) 是否为偶数，以及 \(n/2\) 是否落在斐波那契数里。这些数可以事先放进哈希集合，查询时做一次成员判断。

斐波那契数列定义为 \(F_0=0\)、\(F_1=1\)，以及 \(F_{i+2}=F_i+F_{i+1}\)。连续三项之和满足

\[ F_i+F_{i+1}+F_{i+2}=2F_{i+2}. \]

当 \(i\ge 0\) 时，\(F_{i+2}\) 取遍所有不小于 \(1\) 的斐波那契数。预先生成不超过 \(10^9\) 的斐波那契数，放入哈希集合 \(f\)。\(n\) 为偶数且 \(n/2\in f\) 时返回 \(\text{true}\)，否则返回 \(\text{false}\)。

预处理的时间复杂度与空间复杂度均为 \(O(\log M)\)，单次查询的时间复杂度为 \(O(1)\)。其中 \(M=10^9\)。

Python3JavaC++GoTypeScript

a, b = 0, 1
mx = 10**9 + 1
f = set()
while b < mx:
    a, b = b, a + b
    f.add(b)


class Solution:
    def threeFibonacciSum(self, n: int) -> bool:
        return n % 2 == 0 and n // 2 in f

class Solution {
    static Set<Integer> f = new HashSet<>();

    static {
        int a = 0, b = 1;
        while (b < 1000000001) {
            int c = a + b;
            a = b;
            b = c;
            f.add(b);
        }
    }

    public boolean threeFibonacciSum(int n) {
        return n % 2 == 0 && f.contains(n / 2);
    }
}

class Solution {
    static unordered_set<int> f;

public:
    bool threeFibonacciSum(int n) {
        return n % 2 == 0 && f.count(n / 2);
    }
};

unordered_set<int> Solution::f = [] {
    unordered_set<int> f;
    int a = 0, b = 1;
    while (b < 1000000001) {
        int c = a + b;
        a = b;
        b = c;
        f.insert(b);
    }
    return f;
}();

var f = func() map[int]bool {
    f := map[int]bool{}
    a, b := 0, 1
    for b < 1000000001 {
        a, b = b, a+b
        f[b] = true
    }
    return f
}()

func threeFibonacciSum(n int) bool {
    return n%2 == 0 && f[n/2]
}

const f = new Set<number>();

for (let a = 0, b = 1; b < 1000000001;) {
    [a, b] = [b, a + b];
    f.add(b);
}

function threeFibonacciSum(n: number): boolean {
    return n % 2 === 0 && f.has(n / 2);
}

4078. 连续三项斐波那契数之和

题目描述

解法

方法一：斐波那契数判定

评论