# 两数之和
# 难度：简单
# 描述：
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。
你需要实现的函数 twoSum 需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。
# 样例：
给出 numbers = [2, 7, 11, 15], target = 9, 返回 [0, 1].
给出 numbers = [2, 33, 11, 2], target = 4, 返回 [0, 3].
# 思路分析：
target减去每个元素的值，得出来的值，就是我们要搜索的值。
# 代码模板：
/**
* @param numbers: An array of Integer
* @param target: target = numbers[index1] + numbers[index2]
* @return: [index1, index2] (index1 < index2)
*/
const twoSum = function(numbers, target) {};
1
2
3
4
5
6
2
3
4
5
6
# 想一想再看答案
# 想一想再看答案
# 想一想再看答案
# 代码：
- 转成对象：
这是别人的一种解法，比下面的解法复杂点，可以看看，扩展一下思路。
/**
* @param numbers: An array of Integer
* @param target: target = numbers[index1] + numbers[index2]
* @return: [index1, index2] (index1 < index2)
*/
const twoSum = function(numbers, target) {
let map = {};
// key : the complement (target - num)
// value: index for that num
for (let i = 0; i < numbers.length; i++) {
const num = numbers[i];
if (map[num] !== undefined) {
// 找到值
return [map[num], i]; // 第一次保存的index 和 刚找到的下标 即结果。
} else {
// 第一次进入 保存 要搜索的值和index
map[target - num] = i; // 第一次
}
}
return [-1, -1];
};
console.log(twoSum([2, 7, 11, 15], 9), twoSum([2, 33, 11, 2], 4));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
- 双循环
const twoSum = function(numbers, target) {
for (let index of numbers.keys()) {
let res = target - numbers[index]; // 要搜索的值
for (let i = numbers.length - 1; i > index; i--) {
// 倒序查找，跳过已经遍历过的值
if (res === numbers[i]) return [index, i]; // 搜索到了 即找到
}
}
};
console.log(twoSum([2, 7, 11, 15], 9), twoSum([2, 33, 11, 2], 4));
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
- indexOf()
indexOf的第二个参数是开始搜索的位置，也可以跳过前面已经搜索过的值。
const twoSum = function(numbers, target) {
for (let index of numbers.keys()) {
let res = target - numbers[index]; // 相减
let search = numbers.indexOf(res, index + 1); // 跳过前面已经搜索过的，防止2+2=4 搜索两个2在同一个位置
if (search !== -1) {
return [index, search]; // 直接返回值
}
}
};
console.log(twoSum([2, 7, 11, 15], 9), twoSum([2, 33, 11, 2], 4));
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10