难度: Easy
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
输入：n = 4 输出：3 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
0 <= n <= 100运行时间: 40 ms
内存: 13.3 MB
class Solution:
def fib(self, n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a+b
return a % 1000000007
这个题解采用了迭代的方法来计算斐波那契数列，避免了递归方法中的重复计算问题。它使用两个变量a和b来存储连续的斐波那契数，初始设置为F(0)和F(1)。在每次迭代中，计算当前斐波那契数的下一个数，并更新这两个变量。迭代进行n次，最终返回第n个斐波那契数，并取模1e9+7以防止整数溢出。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def fib(self, n: int) -> int:
a, b = 0, 1 # 初始化F(0)和F(1)
for _ in range(n): # 循环n次，计算第n个斐波那契数
a, b = b, a+b # 更新a和b到下一对斐波那契数
return a % 1000000007 # 返回结果并取模以防整数溢出
在计算斐波那契数时，递归方法虽然直观，但它会导致大量重复的计算，特别是在计算较大的斐波那契数时，这会导致指数级的时间复杂度。每个斐波那契数都会被多次重新计算，因此效率很低。相比之下，迭代方法只需线性时间即可计算出结果，因为它从最基本的数开始，逐步构建至目标位置，无需重复计算，更加高效。
在迭代方法中，使用两个变量a和b来存储连续的斐波那契数（即F(n-1)和F(n)）的目的是为了在每次迭代中有效计算下一个斐波那契数F(n+1)。这种方法避免了需要使用额外空间存储整个斐波那契数列，从而减少空间复杂度到O(1)，即常数级空间。
在每次迭代过程中，变量b更新为a+b是为了计算当前斐波那契数的下一个数F(n+1)，而更新a为原来的b是为了将当前的F(n)（即旧的b）移动到F(n-1)的位置，为下一轮计算做准备。这样，a和b始终保持为连续的两个斐波那契数，确保迭代可以正确进行。
斐波那契数列增长非常快，当n较大时，计算得到的斐波那契数可能会超出标准整数类型（如int或long）的存储范围，导致整数溢出。在算法中使用取模操作（模1e9+7，一个大质数），是为了保证结果始终在一个安全的可表示范围内，并且可以避免溢出。此外，取模操作通常与某些编程比赛或算法问题中的要求相关，以确保结果的一致性和比较。