简单

1. 两数之和

序号：1
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：

  1. 输入：nums = [2,7,11,15], target = 9
  2. 输出：[0,1]
  3. 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

  1. 输入：nums = [3,2,4], target = 6
  2. 输出：[1,2]

示例 3：

  1. 输入：nums = [3,3], target = 6
  2. 输出：[0,1]

题解：

哈希表

维护一个哈希表，key是数字，value为下标，遍历数组，判断(目标值-当前数)的值是否存在哈希表里，存在则返回对应的下标，不存在则把当前数字放入哈希表

  1. var tomSum = function(nums, target) {
  2.     // 存 数字 => 下表 键值对
  3.   let hashMap = new Map();
  5.   for (let i = 0; i < nums.length; i++) {
  6.       const another = target - nums[i];
  7.     const isHas = hashMap.has(another);
  8.     if (isHas) {
  9.         return [hashMap.get(another), i];
  10.     }
  11.     hashMap.set(nums[i], i);
  12.   }
  13.   return [];
  14. }

或者

  1. var tomSum = function(nums, target) {
  2.     let obj = {};
  3.   for (let i = 0; i < nums.length; i++) {
  4.       let another = target - nums[i];
  5.     if (another in obj) {
  6.         return [obj[another], i];
  7.     }
  8.     obj[nums[i]] = i;
  9.   }
  10.   return [];
  11. }

复杂度：

  • 时间复杂度O(N)

  • 空间复杂度O(N)

    双重for循环

    1. var tomSum = function(nums, target) {
    2.   for (let i = 0; i < nums.length; i++) {
    3.   for (let j = i + 1; j < nums.length; j++) {
    4.       if ((nums[i) + nums[j] === target) && (i !== j)) {
    5.         return [i, j];
    6.     }
    7.   } 
    8. }
    9. return [];
    10. }

    复杂度：

  • 时间复杂度O(N^2)

  • 空间复杂度O(1)

    4. 寻找两个正序数组的中位数

    序号：4
    给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
    算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

  1. 输入：nums1 = [1,3], nums2 = [2]
  2. 输出：2.00000
  3. 解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

  1. 输入：nums1 = [1,2], nums2 = [3,4]
  2. 输出：2.50000
  3. 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

题解：

合并数组排序

  1. /**
  2. * @param {number[]} nums1
  3. * @param {number[]} nums2
  4. * @return {number}
  5. */
  6. var findMedianSortedArrays = function(nums1, nums2) {
  7.   const newArray = nums1.concat(nums2).sort(function(a, b){return a - b});
  8.   const length = newArray.length;
  9.   if (length % 2 === 0) {
  10.     const num = length / 2;
  11.     return (newArray[num -1] + newArray[num]) / 2;
  12.   }
  13.   let num = Math.ceil(length / 2) - 1;
  14.   return newArray[num];
  15. };

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1：

  1. 输入：strs = ["flower","flow","flight"]
  2. 输出："fl"

示例 2：
题解：

双重循环

  1. /**
  2.  * @param {string[]} strs
  3.  * @return {string}
  4.  */
  5. var longestCommonPrefix = function(strs) {
  6.     if (strs.length === 0) {
  7.         return "";
  8.     }
  9.     let ans = strs[0];
  10.     for (let i = 1; i < strs.length; i++) {
  11.         let j = 0;
  12.         for (; j < ans.length && j < strs[i].length; j++) {
  13.             if (ans[j] != strs[i][j]) {
  14.                 break;
  15.             }
  16.         }
  17.         ans = ans.substr(0, j);
  18.         if (ans === "") {
  19.             return ans;
  20.         }
  21.     }
  22.     return ans;
  23. };


20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1：

  1. 输入：s = "()"
  2. 输出：true

示例 2：

  1. 输入：s = "()[]{}"
  2. 输出：true

示例 3：

  1. 输入：s = "(]"
  2. 输出：false

示例 4：

  1. 输入：s = "([)]"
  2. 输出：false

示例 5：

  1. 输入：s = "{[]}"
  2. 输出：true

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 ‘()[]{}’ 组成

题解：

栈

  1. // 执行用时 64ms 内存消耗 41.3MB
  2. /**
  3. * @param {string} s
  4. * @return {boolean}
  5. */
  6. var isValid = function(s) {
  7.   const n = s.length;
  8.   if (n % 2 === 1) {
  9.     return false;
  10.   }
  11.   // const pairs = {
  12.   //  "}": "{",
  13.   //  "]": "[",
  14.   //     ")": "("
  15.   // }
  16.   const pairs = new Map([
  17.     [')', '('],
  18.     [']', '['],
  19.     ['}', '{']
  20.   ]);
  21.   const stk = [];
  22.   for (let ch of s){
  23.     if (pairs.has(ch)) { // // pairs.has(ch) => obj[ch]
  24.       if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) { // // pairs.get(ch) => obj[ch]
  25.         return false;
  26.       }
  27.       stk.pop();
  28.     } 
  29.     else {
  30.       stk.push(ch);
  31.     }
  32.   };
  33.   return !stk.length;
  34. };

或者 类似的写法：

  1. var isValid = function(s) {
  2.     const stack = [];
  4.     for (let i = 0; i < s.length; i++) {
  5.         if (['(', '{', '['].includes(s[i])) {
  6.             stack.unshift(s[i]);
  7.         } else if (['()', '{}', '[]'].includes(stack[0] + s[i])) {
  8.             stack.shift();
  9.         } else {
  10.             return false;
  11.         }
  12.     }
  14.     return stack.length == 0;
  15. };

复杂度分析

  • 时间复杂度：O(n)，其中 nn 是字符串 ss 的长度。
  • 空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。

    26. 删除有序数组中的重复项

    序号：26
    给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：

  1. 输入：nums = [1,1,2]
  2. 输出：2, nums = [1,2]
  3. 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

  1. 输入：nums = [0,0,1,1,1,2,2,3,3,4]
  2. 输出：5, nums = [0,1,2,3,4]
  3. 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

  1. 0 <= nums.length <= 3 * 104
  2. -104 <= nums[i] <= 104
  3. nums 已按升序排列

题解：

双指针

如果数组nums 的长度为 0，则数组不包含任何元素，因此返回 0。

当数组 nums 的长度大于 0 时，数组中至少包含一个元素，在删除重复元素之后也至少剩下一个元素，因此nums[0] 保持原状即可，从下标 1 开始删除重复元素。

定义两个指针 fast 和 slow 分别为快指针和慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标 1。

假设数组nums 的长度为 n。将快指针fast 依次遍历从 1到 n-1的每个位置，对于每个位置，如果 nums[fast] / nums[fast−1]，说明 nums[fast] 和之前的元素都不同，因此将 nums[fast] 的值复制到 nums[slow]，然后将 slow 的值加 1，即指向下一个位置。

遍历结束之后，从 nums[0] 到nums[slow−1] 的每个元素都不相同且包含原数组中的每个不同的元素，因此新的长度即为 slow，返回 slow 即可。

题解：

  1. /**
  2. * @param {number[]} nums
  3. * @return {number}
  4. */
  5. var removeDuplicates = function(nums) {
  6.   const n = nums.length;
  7.   if (n === 0) {
  8.     return 0;
  9.   }
  10.   let fast = 1, slow = 1;
  11.   while (fast < n) {
  12.     if (nums[fast] !== nums[fast -1]) {
  13.       nums[slow] = nums[fast];
  14.       ++slow;
  15.     }
  16.     ++fast;
  17.   }
  18.   return slow;
  19. }

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。
  • 空间复杂度：O(1)。只需要使用常数的额外空间。

    53. 最大子数组和

    序号：53
    给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    子数组 是数组中的一个连续部分。

示例 1：

  1. 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
  2. 输出：6
  3. 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

  1. 输入：nums = [1]
  2. 输出：1

示例 3：

  1. 输入：nums = [5,4,-1,7,8]
  2. 输出：23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

题解：

动态规划

若前一个元素大于0，则将其加到当前元素上。

  1. 原数组：[-2, 1, -3, 4, -1, 2, 1, -5, 4];
  2. 新数组：[-2, 1, -2, 4, 3, 5, 6, 1, 5];
  3. 取新数组的最大值
  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. // 判断前一个值是否大于0，形成新数组
  6. // 执行用时：68 ms  内存消耗：49.7 MB
  7. var maxSubArray = function(nums) {
  8.     const n = nums.length;
  9.     for (let i = 1; i < n; i++) {
  10.         if (nums[i - 1] > 0) {
  11.             nums[i] += nums[i -1];
  12.         } 
  13.     }
  14.     return Math.max(...nums);
  15. };

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 nums 数组的长度。
  • 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

    贪心算法

    若当前指针所指元素之前的和小于0.则丢弃当前元素之前的数列 ```javascript 旧数组：[-2, 1, -3, 4, -1, 2, 1, -5, 4];
  1. -2 + 0 < 0; 丢弃
  2. 1 + 0 > 0; 保留 当前和为1
  3. 1 + -3 < 0; 丢弃
  4. 4 + 0 > 0; 保留 …
    1. ```javascript
    2. var maxSubArray = function(nums) {
    3.  let pre = 0, maxAns = nums[0];
    4.  nums.forEach((x) => {
    5.      pre = Math.max(pre + x, x);
    6.      maxAns = Math.max(maxAns, pre);
    7.  });
    8.  return maxAns;
    9. };
    复杂度分析
  • 时间复杂度：O(n)，其中 n 为 nums 数组的长度。
  • 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

    71. 简化路径

    题号：71
    给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/‘ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//‘）都被视为单个斜杠 ‘/‘ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 ‘/‘ 开头。
两个目录名之间必须只有一个斜杠 ‘/‘ 。
最后一个目录名（如果存在）不能 以 ‘/‘ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘..’）。
返回简化后得到的 规范路径 。

示例 1：

  1. 输入：path = "/home/"
  2. 输出："/home"
  3. 解释：注意，最后一个目录名后面没有斜杠。

示例 2：

  1. 输入：path = "/../"
  2. 输出："/"
  3. 解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

  1. 输入：path = "/home//foo/"
  2. 输出："/home/foo"
  3. 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

  1. 输入：path = "/a/./b/../../c/"
  2. 输出："/c"

栈

  1. /**
  2.  * @param {string} path
  3.  * @return {string}
  4.  */
  5. var simplifyPath = function(path) {
  6.     const names = path.split("/");
  7.     const stack = [];
  8.     for (const name of names) {
  9.         if (name === "..") {
  10.             if (stack.length) {
  11.                 stack.pop();
  12.             } 
  13.         } else if (name.length && name !== ".") {
  14.             stack.push(name);
  16.         }
  17.     }
  19.     return "/" + stack.join("/");
  20. };

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 path 的长度。
  • 空间复杂度：O(n)。我们需要 O(n)的空间存储 names 中的所有字符串。

第二种：

  1. var simplifyPath = function(path) {
  2.     const dir = path.split('/'), stack = []
  3.     for(let name of dir) {
  4.         if(name === '.' || name === '') continue;
  5.         if(name === '..') {
  6.             stack.length && stack.pop();
  7.             continue;
  8.         }
  9.         stack.push(name)
  10.     }
  11.     return '/' + stack.join('/')
  12. };

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

  1. 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
  2. 输出：[1,2,2,3,5,6]
  3. 解释：需要合并 [1,2,3] 和 [2,5,6] 。
  4. 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

  1. 输入：nums1 = [1], m = 1, nums2 = [], n = 0
  2. 输出：[1]
  3. 解释：需要合并 [1] 和 [] 。
  4. 合并结果是 [1] 。

示例 3：

  1. 输入：nums1 = [0], m = 0, nums2 = [1], n = 1
  2. 输出：[1]
  3. 解释：需要合并的数组是 [] 和 [1] 。
  4. 合并结果是 [1] 。
  5. 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

题解：

直接合并后排序

  1. /**
  2.  * @param {number[]} nums1
  3.  * @param {number} m
  4.  * @param {number[]} nums2
  5.  * @param {number} n
  6.  * @return {void} Do not return anything, modify nums1 in-place instead.
  7.  */
  8. var merge = function(nums1, m, nums2, n) {
  9.   nums1.splice(m, nums1.length - m, ...nums2);
  10.   nums1.sort((a, b) => a -b);
  11. };

复杂度分析

  • 时间复杂度：O((m+n)log(m+n))。排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log(m+n))。

  • 空间复杂度：O(log(m+n))。排序序列长度为 m+nm+n，套用快速排序的空间复杂度即可，平均情况为 O(log(m+n))。

    双指针

    讲解

  • 首先判断ptr1是否走完nums1，或者ptr2是否走完nums2,如果一个数组走完则将剩余数组全部接在sorted后面；

  • 当nums1[ptr1] <= nums2[ptr2]时，将nums1[ptr1]赋值给临时变量cur, ptr1++；
  • 否则，将nums2[ptr2]赋值给临时变量cur, ptr2++；
  • sorted数组当前的位置是ptr1 + ptr2 - 1, 因为上一步将指针++了，但是并未赋值，所以sorted[ptr1 + ptr2 - 1] = cur；

  • 最后将sorted每一个位置一一赋值给nums1;

    1. var merge = function(nums1, m, nums2, n) {
    2. let p1 = 0, p2 = 0;
    3. const sorted = new Array(m + n).fill(0);
    4. var cur;
    5. while (p1 < m || p2 < n) {
    6.   if (p1 === m) {
    7.     cur = nums2[p2++];
    8.   } else if (p2 === n) {
    9.     cur = nums1[p1++];
    10.   } else if (nums1[p1] < nums2[p2]) {
    11.     cur = nums1[p1++];
    12.   } else {
    13.     cur = nums2[p2++];
    14.   }
    15.   sorted[p1 + p2 - 1] = cur;
    16. }
    17. for (let i = 0; i != m + n; ++i) {
    18.   nums1[i] = sorted[i];
    19. }
    20. };

    复杂度分析

  • 时间复杂度：O(m+n)。指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。

  • 空间复杂度：O(m+n)。需要建立长度为 m+n 的中间数组 sorted。

    逆向双指针

    1. var merge = function(nums1, m, nums2, n) {
    2.   let p1 = m - 1, p2 = n - 1;
    3.   let tail = m + n - 1;
    4.   var cur;
    5.   while (p1 >= 0 || p2 >= 0) {
    6.       if (p1 === -1) {
    7.           cur = nums2[p2--];
    8.       } else if (p2 === -1) {
    9.           cur = nums1[p1--];
    10.       } else if (nums1[p1] > nums2[p2]) {
    11.           cur = nums1[p1--];
    12.       } else {
    13.           cur = nums2[p2--];
    14.       }
    15.       nums1[tail--] = cur;
    16.   }
    17. };

    复杂度分析

  • 时间复杂度：O(m+n)。指针移动单调递减，最多移动 m+n 次，因此时间复杂度为 O(m+n)。

  • 空间复杂度：O(1)。直接对数组 nums1 原地修改，不需要额外空间。

439. 两个数组的交集

序号：439
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

  1. 输入：nums1 = [1,2,2,1], nums2 = [2,2]
  2. 输出：[2]

示例 2：

  1. 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
  2. 输出：[9,4]
  3. 解释：[4,9] 也是可通过的

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

题解：

两个集合

  1. /**
  2. * @param {number[]} nums1
  3. * @param {number[]} nums2
  4. * @return {number[]}
  5. */
  6. var intersection = function(nums1, nums2) {
  7.   const set1 = new Set(nums1);
  8.   const set2 = new Set(nums2);
  9.   if (set1.size > set2.size) {
  10.     [set1, set2] = [set2, set1];
  11.   }
  12.   const intersetion = new Set();
  13.   for (const num of set1) {
  14.     if (set2.has(num)) {
  15.       intersetion.add(num);
  16.     }
  17.   }
  18.   return [...intersetion];
  19. };

复杂度分析

  • 时间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要 O(m+n)的时间，遍历较小的集合并判断元素是否在另一个集合中需要 O(min(m,n)) 的时间，因此总时间复杂度是 O(m+n)。
  • 空间复杂度：O(m+n)，其中 m 和 n 分别是两个数组的长度。空间复杂度主要取决于两个集合。

    排序 + 双指针

    如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 pre 表示上一次加入答案数组的元素。

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于pre ，将该数字添加到答案并更新 pre 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

  1. var intersection = function(nums1, nums2) {
  2.   nums1.sort((x, y) => x - y);
  3.   nums2.sort((x, y) => x - y);
  4.   const length1 = nums1.length, length2 = nums2.length;
  5.   let index1 = 0, index2 = 0;
  6.   const intersection = [];
  7.   while (index1 < length1 && index2 < length2) {
  8.     const num1 = nums1[index1], num2 = nums2[index2];
  9.     if (num1 === num2) {
  10.       // 保证加入元素的唯一性
  11.       if (!intersection.length || num1 !== intersection[intersection.length - 1]) {
  12.         intersection.push(num1);
  13.       }
  14.       index1++;
  15.       index2++;
  16.     } else if (num1 < num2) {
  17.       index1++;
  18.     } else {
  19.       index2++;
  20.     }
  21.   }
  22.   return intersection;
  23. };

复杂度分析

  • 时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是两个数组的长度。对两个数组排序的时间复杂度分别是 O(mlogm) 和 O(nlogn)，双指针寻找交集元素的时间复杂度是 O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。
  • 空间复杂度：O(logm+logn)，其中 m 和 n 分别是两个数组的长度。空间复杂度主要取决于排序使用的额外空间。

    509. 斐波那契数

    序号：509
    斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
    1. F(0) = 0，F(1) = 1
    2. F(n) = F(n - 1) + F(n - 2)，其中 n > 1
    给定 n ，请计算 F(n) 。

示例1:

  1. 输入：n = 2
  2. 输出：1
  3. 解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例2:

  1. 输入：n = 3
  2. 输出：2
  3. 解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例3:

  1. 输入：n = 4
  2. 输出：3
  3. 解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

  • 0 <= n <= 30

题解：

动态规划

  1. var fib = function(n) {
  2.     if (n < 2) {
  3.       return n;
  4.   }
  6.   let p = 0, q = 0, r= 1;
  7.   for (let i = 2; i <= n; i++) {
  8.       p = 1;
  9.     q = r;
  10.     r = p + q;
  11.   }
  13.   return r;
  14. }

复杂度分析

  • 时间复杂度：O(n)。

  • 空间复杂度：O(1)。

    暴力递归

    1. var fib = function(n) {
    2.   if (n < 2) {
    3.     return n;
    4. }
    6. return fib(n-1) + fib(n-2);
    7. }

    递推

    1. var fib = function(n) {
    2. let array = [];
    3.   for (let i = 0; i <= n; i++) {
    4.     if (n < 2) {
    5.     array[i] = i;
    6.   } else {
    7.       array[i] = array[i - 1] + array[i - 2];
    8.   }
    9. }
    10. return array[n];
    11. }

    复杂度分析

  • 时间复杂度：O(n)。

  • 空间复杂度：O(1)。

中等