C++实现非递归斐波那契函数出现vector下标越界错误求解

• std::vector的operator[]不具备自动扩容能力，你初始化的array只有2个元素（对应下标0、1），当i>=2时直接执行array[i] = ...属于访问未申请的内存空间，直接触发越界。
• 循环逻辑存在错误，你设置的循环终止条件是i < num，当需要获取第num项斐波那契值时，循环执行完成后array的最大下标仍然小于num，后续执行return array[num]时必然访问到不存在的下标。
• 代码存在基础语法缺失：main函数中使用cout没有加std::命名空间限定，也没有引入<iostream>、<vector>头文件，无法正常编译。

1. 改用push_back方法向vector添加元素，push_back会自动完成内存扩容
2. 调整循环终止条件，补充边界值的特殊处理
3. 补全头文件和命名空间限定

修正后的可运行代码如下：

#include <iostream>
#include <vector>

int fib(const int num)
{
    // 边界值特殊处理
    if (num == 0) return 0;
    if (num == 1) return 1;
    std::vector<int> array{ 0, 1 };
    // 循环到i等于num，保证计算到目标项
    for (int i = 2; i <= num; ++i)
    {
        array.push_back(array[i - 1] + array[i - 2]);
    }
    return array[num];
}

int main()
{
    const int n = 10;
    for (int i = 0; i <= n; ++i)
    {
        std::cout << fib(i) << " ";
    }
    return 0;
}

如果不需要存储所有历史斐波那契值，可以用两个变量滚动存储前两项，将空间复杂度从O(n)降低到O(1)，示例实现：

int fib(const int num)
{
    if (num == 0) return 0;
    if (num == 1) return 1;
    int prev_prev = 0, prev = 1, res;
    for (int i = 2; i <= num; ++i)
    {
        res = prev_prev + prev;
        prev_prev = prev;
        prev = res;
    }
    return res;
}

内容的提问来源于stack exchange，提问作者MZO