题解 | #斐波那契数列#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param n int整型 
 * @return int整型
 */
export function Fibonacci(n: number): number {
    // 解法一：递归
    // 时间复杂度 O(2^n)
//     if (n === 0) return 0
//     if (n === 1) return 1
    
//     return Fibonacci(n - 1) + Fibonacci(n - 2)
    
    // 解法二：循环
    // 时间复杂度 O(n)
    if (n <= 0) return 0
    if (n === 1) return 1

    let n1 = 1 // 记录 n - 1 的结果
    let n2 = 0 // 记录 n - 2 的结果
    let res = 0

    for (let i = 2; i <= n; i++) {
        res = n1 + n2

        // 记录中间结果
        n2 = n1
        n1 = res
    }

    return res
}