题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
1
2
3
2
3
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
1
2
2
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
1
2
2
解法
双 for
第一个想到的就是 for 两次，然后做判断。 这个没啥可说的，暴力解法，穷举+判断即可。
let twoSum = function(nums, target) {
let len = nums.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (target == nums[i] + nums[j] && i !== j) {
return [i, j];
}
}
}
};
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
思路：循环+判断
复杂度
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
静态 Map
因为描述有说，他的值不可用两次，就想到了可以用 ES6 的 Set 数据结构，先把所有的值转为 Set，相当于做了一个去重，然后在求和。
后来发现 Set 存上了，索引怎么取？不如直接用对象，但是对象的键只能为字符串，后面还得做一次数值转换。
看了评论去大神的写法，换用了 Map，新知识 Get！
let twoSum = function(nums, target) {
let len = nums.length;
let map = new Map();
for (let i = 0; i < len; i++) {
map.set(nums[i], i);
}
for (let j = 0; j < len; j++) {
let diff = target - nums[j];
if (map.has(diff) && map.get(diff) !== j) {
return [j, map.get(diff)];
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
思路：
- 先将 nums 转为 Map 类型的，值为健，健为值。
- 然后 for nums 时判断 map 中是否存在 diff
- 有 diff 在判断是否索引一样，如果不一样，直接 return，否则继续
复杂度
- 时间复杂度：O(m+n)
- 空间复杂度：O(1)
动态 Map
其实把上面的改一改，在每次 for 的时候，判断是否有差值，如果就去判断，有没就去添加。
这样 for 一次就可以了。
let twoSum = function(nums, target) {
let len = nums.length;
let map = new Map();
for (let i = 0; i < len; i++) {
console.log(i, nums[i]);
let diff = target - nums[i];
if (map.has(diff) && map.get(diff) !== i) {
return [map.get(diff), i];
} else {
map.set(nums[i], i);
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
思路：
- 和上面的差不多，不过是一边 for 的时候做 diff 判断
- 无 diff 去 set
- 有 diff 判断即可
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(1)
总结
Map：以前只是文档看过，对于它的应用场景一直很模糊，实际工作中基本没有用到，这次也算是熟悉一些。
这次也算是加深了印象，对于应用场景也有了一些了解。