---
# System prepended metadata

title: '-Nth Fibonacci'
tags: [Easy]

---

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

![](https://i.imgur.com/0lMNuhP.png)

想法一：遞迴解 (O(N^2)) time
```cpp=
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
```cpp=
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];
}
```