# -Nth Fibonacci
###### tags: `Easy`


想法一：遞迴解 (O(N^2)) time

using namespace std;

int getNthFib(int n) {
  // Write your code here.
  if (n == 1) return 0;
  if (n == 2) return 1;
  if (n >= 3) return getNthFib(n-1) + getNthFib(n-2); 
  return -1;
}

想法二：用unordered_map存值(略）... O(N)space

想法三：迴圈求解: (O(N)) time, O(1)space

int getNthFib(int n) {
  // Write your code here.
  int lastTwo[] = {0,1};
  int counter = 3;
  while (counter <= n){
      int nextFib = lastTwo[0] + lastTwo[1];
      lastTwo[0] = lastTwo[1];
      lastTwo[1] = nextFib;
      counter++;
  }
  return n > 1 ? lastTwo[1]:lastTwo[0];
}