1. 题目
  2. 思路
  3. 优化
  4. 参考

1. Two Sum

题目

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)