斐波那契数列

ryluo 2020-06-22 21:39:44

输入一个整数 n ,求斐波那契数列的第 nn项。

假定从0开始,第0项为0。(n<=39)

样例

输入整数 n=5 

返回 5

分析:

注意从第0项开始,并且第0项为0,即:

0, 1, 1, 2, 3, 5 …

使用滚动的变量直接进行求解,时间复杂度为O(n) 空间复杂度为O(1)

class Solution {
public:
    int Fibonacci(int n) {
        int a = 0, b = 1;
        while(n -- ){
            int c = a + b;
            a = b, b = c;
        }

        return a;
    }
};