LintCode 查找斐波纳契数列中第 N 个数

查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指：

• 前2个数是 0 和 1 。
• 第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

 

class Solution {

    /**

     * @param n: an integer

     * @return an integer f(n)

     */

    public int fibonacci(int n) {

        // write your code here

        /*  递归 超时，时间有限制，不能通过测评

        // 测试提示：你的代码运行时间超过了限制，检查你的时间复杂度。

        //   TLE通常是由死循环造成的，思考一下你的时间复杂度是否是最优的。

        if(n>=1){

            if(n==1||n==2){

                return n-1;

            }else{

                return fibonacci(n-1)+fibonacci(n-2);

            }

            

        }else{ 

           return -1;

        }

        */

      

        //枚举法 效率高

        if(n<=0){

            return -1;

        }else if(n==1||n==2){

            return n-1;

        }else{

            int s1=0;

            int s2=1;

            int sum=0;

            for(int i=3;i<=n;i++){

                sum=s1+s2;

                s1=s2;

                s2=sum;

            }

            return sum;

        }

        

    }

}