“ 说到算法头就大，但是想要找到好的工作就必须多刷LeetCode上面的题，今天就先来一道简单的题作为下酒菜，后续慢慢不断自我提升，也请有更好想法的小伙伴欢迎在下面留言评论。”
1. 时间复杂度和空间复杂度
在开启算法之旅的时候，我需要顺带提一句时间复杂度和空间复杂度的问题。关于时间复杂度指：执行当前算法所消耗的时间；空间复杂度指：执行当前算法所需要占用的内存空间。在我们做算法题的时候，对这两个的考虑是十分重要的，有时候你感觉自己写的代码没有问题，但是在机器上运行的时候就会发现超时或者内存溢出的问题，这个时候你就需要考虑自己写的代码是否是完美的。
时间复杂度和空间复杂度密不可分，包括在我们工作中写项目也是，一般都采用时间换空间，或者空间换时间，毕竟鱼和熊掌不可兼得。
在这里我就不介绍时间复杂度和空间复杂度是什么、以及它们的相关应用是什么，在网上一搜一大堆相关的帖子和文章，都是很容易懂的。
2. 两数之和
这可能是leetcode里面很简单的一道题目了，但是一步一个脚印慢慢成长，不可能一口吃成一个大胖子。
接下来说一下题目，我直接上图，请看下图：
看到这道题，我最原始、最low的方法就是双重for循环，但是这个时候时间复杂度会很大，为O(n^2)，这里我就不讲这种很大家都会的方法了。
思考：能不能将时间复杂度降低为O(n)?
答案：当然可以。
3. 方法一之利用Map
看题目最后输出的是索引，考虑到使用到索引以及值；查找的两个数位置肯定是固定，即第一个数永远在第二个数前面，因此我们可以使用一层for循环进行遍历。这个时候就考基础的时候了，要用到索引，并且索引要对应到其值（起到隐射关系），那么就可以延展中Map对象。
ps：如果你对Map对象不是很熟悉的话，那么建议你看看Map的MDN文档。
思路：
定义变量map为Map对象，用于做映射，使用一层for循环，假设定义循环中的变量为i，那么第一个数我们给它固定为nums[i]，这个时候由于是两数的和为target，那么另外一个数的值temp为target-nums[i]，Map对象中有has方法表示：是否包含键对应的值。如果包含那么就返回[i, temp值对应的索引]，相反就设置map的映射索引和value值的对应关系。说了这么多，下面就看看代码怎么实现的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| /**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const len = nums.length;
let map = new Map();
let result = [];
for (let i = 0; i < len; i++) {
let temp = target - nums[i];
if (map.has(temp)) {
result[0] = map.get(temp);
result[1] = i;
return result;
} else {
map.set(nums[i], i);
}
}
};
|
4. 方法二
方法二和方法一有点类似，但是方法二没有使用Map对象，由于考虑到key和value做映射，这个时候就可以借助哈希表，下面放代码给大家看看。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| /**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const len = nums.length;
let result = [];
let temp;
for (let i = 0; i < len; i++) {
temp = target - nums[i];
if (result[temp] !== undefined) {
return [result[temp], i];
}
result[nums[i]] = i;
}
};
|
