求斐波那契数列第n个值

前言

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

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

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

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

样例
样例 1:
输入: 1
输出: 0

样例解释: 
返回斐波那契的第一个数字,是0.

样例 2:
输入: 2
输出: 1

正文

时间复杂度O(n)

空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package io.since1986.demo;

public class Solution {

public int fibonacci(int n) {
int result = 0;

// 初始为 0,1
int oneElement = 0;
int nextOneElement = 1;

// index 应从3开始,因为第1个值oneElement和第2个值nextOneElement已经事先给出了,如果index从1开始那么就重复计算了两次
for (int index = 3; index <= n; index++) {
// 当次结果
result = oneElement + nextOneElement;

// 下一次的 oneElement 应该变成其后边的元素,也就是 nextOneElement
oneElement = nextOneElement;

// 下一次的 nextOneElement 应该变成其后边的元素,也就是 result
nextOneElement = result;

// 进入下轮
}

return result;
}
}