LeetCode

题目 地址：https://leetcode.cn/problems/two-sum/ 思路 通过 Map 把数组的每一项进行缓存 （key 为数组中的项，value 为索引），然后再对数组进行遍历，并计算是否存在 key 相加等于目标值 遍历数组，判断差值是否存在 Map 中 如果存在，返回对应的索引 如果不存在，将这一项添加到 Map 中 数组遍历结束，返回一个兜底的数组 [-1, -1] /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function (nums, target) { const map = new Map(); for (let i = 0; i < nums.length; i++) { const item = nums[i]; const different = target - item; if (map.get(different) !== undefined) { return [map....

题目 地址：https://leetcode.cn/problems/fibonacci-number/ 解题 斐波那契数列的特点是由后两个数字相加得出下一个数字， 首先能想到的就是用递归来解决。 递归的出口是 F(0) = 0，F(1) = 1 找到出口之后就很简单了，三下五除二就写出来： var fib = function (n) { if (n <= 1) { return n; } function add(num) { if (num === 1 || num === 0) { return num; } else { return add(num - 1) + add(num - 2); } } return add(n); }; 愉快的提交之后， 嚯，击败了 14% 的提交。 优化 由于盲目的使用递归，造成了大量的重复操作，时间复杂度是 O(2^n)，指数级爆炸。 自顶而下 为了解决这些重复的操作，使用 memoization 的思想来对已计算的数据进行缓存。 下面来用 数组 实现一下：...