斐波纳契数列

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

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

前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：

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

import java.util.*;
class Solution {
    /**
     * @param n: an integer
     * @return an integer f(n)
     */
    public int fibonacci(int n) {
        // write your code here
        //定义第n个斐波那契数为sum
        int sum = 0;
        if(n == 1){
            //n为1时直接返回0
            sum = 0;
        } else if(n == 2){
            //n为2时直接返回1
            sum = 1;
        } else {
            //从第三个数开始使用List来处理
            ArrayList<Integer>list = new ArrayList<Integer>();
            //list中添加第一个斐波那契数
            list.add(0);
            //list中添加第二个斐波那契数
            list.add(1);
            //list中添加第n(n>=3)个斐波那契数
            for(int i = 3; i <= n; i++){
                //第 n 个数是第 n-1 个数和第n-2 个数的和
                //因为list下标从0开始，第 i 个数实际为第 i-2 个数和第i-3 个数的和
                list.add(list.get(i-2)+list.get(i-3));
                //斐波那契数中的第n个数在list中为i-1
                sum = list.get(i-1);
            }
        }
        return sum;
    }
}