【牛客刷题】NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。 为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。如果第n个斐波那契大于6位则只取后6位。

试题链接：斐波那契凤尾__牛客网

先贴代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int border = -1; // 记录下第一个大于六位数的斐波那契数的下标
        long[] ans = new long[100000]; // 创建数组
        ans[0] = 1;
        ans[1] = 2;
        for (int i = 2; i < 100000; i++) {
            long next = ans[i - 1] + ans[i - 2];
            if (border == -1 && next >= 1000000) {
                border = i + 1; // 当有第一个next大于六位数时，border记录下它的坐标
            }
            ans[i] = next % 1000000; // 模上 1000000 表示取后6位，有几个0，表示取后几位！
        }

        Scanner s = new Scanner(System.in);
        while (s.hasNextInt()) {
            // 输入n：
            int n = s.nextInt();

            long f = ans[n - 1];
            if (n < border) {
                System.out.printf("%d\n", f); // 整数正常输出
            } else {
                System.out.printf("%06d\n", f); // 整数输出，宽度为6，不足处左边补0
            }
        }
    }
}

解题思路：

        题目告诉我们它记住了 1~100000 之间的所有斐波那契数，所以整个题目的区间就是1~10000，要求我们输出第 n 个斐波那契数，如果大于6位则输出后6位即可。

        由上可知，n 的范围是 1~100000 ，所以我们可以先创建一个数组，容量就为100000，在这个数组里存储每个斐波那契数或者它的后六位。不过要注意，我们创建数组时要创建 long 长整型数组！

        然后开始往这个数组里填入数据，数据为斐波那契数，不过我们需要另外设置一个边界值 border ，这个边界值作用是标记这个数组里的第一个超过六位数的斐波那契数的下标，方便我们之后输出，如果遍历数组时，下标小于这个边界值 border ，那么说明该下标的斐波那契数是不足六位或者是正好六位数的，此时直接输出即可，反之则说明该数是大于六位数的，这时候就得取它的后六位输出。

        设置好之后就可以根据输入的 n 来输出对应的第 n 个斐波那契数了。