题目
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
1
2
3
4
| Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
|
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
思路
遍历数组, 储存到哈希表中. 然后再次遍历数组, 取 target 和数组项的差, 查表即可.
复杂度 2n
需考虑的特殊情况:
1 相同的值,例如 [3,3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| const twoSum = function(nums, target) {
const map = {};
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
if (!map[num]) {
map[num] = [];
}
map[num].push(i);
}
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
const difference = target - num;
if (difference === num) {
if (map[num].length > 1) {
return map[num];
}
} else {
if (map[difference]) {
return [map[num][0], map[difference][0]];
}
}
}
};
|
优化
题目要求是求两数之和, 因此对应的差值(上文代码中的 difference)只有一个.
没必要考虑存在多个相同值的特殊情况, 只需遍历一遍,遍历时查找哈希表中是否有对应的差值.有则返回, 没有则将减数添加到哈希表里.
复杂度 n
1
2
3
4
5
6
7
8
9
10
11
12
13
| const twoSum = function(nums, target) {
const map = {};
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
const difference = target - num;
const differenceI = map[difference];
if (differenceI !== undefined) {
return [differenceI, i]
}
map[num] = i
}
};
|
另外,也可以用 Map .不好说哪个性能更好.
1
2
3
4
5
6
7
8
9
10
11
12
| const twoSum = function(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
const difference = target - num;
const differenceI = map.get(difference);
if (differenceI !== undefined) {
return [differenceI, i];
}
map.set(num, i);
}
};
|
参考
Neat-JavaScript-Map-O(n)