算法_两数之和

两数之和

难度:简单

描述:

给一个整数数组,找到两个数使得他们的和等于一个给定的数 target。

你需要实现的函数 twoSum 需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。

样例:

给出 numbers = [2, 7, 11, 15], target = 9, 返回 [0, 1].

给出 numbers = [2, 33, 11, 2], target = 4, 返回 [0, 3].

思路分析:

target减去每个元素的值,得出来的值,就是我们要搜索的值。

代码模板:

1
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) {};

想一想再看答案

想一想再看答案

想一想再看答案

代码:

  1. 转成对象:

这是别人的一种解法,比下面的解法复杂点,可以看看,扩展一下思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @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. 双循环
1
2
3
4
5
6
7
8
9
10
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. indexOf()

indexOf的第二个参数是开始搜索的位置,也可以跳过前面已经搜索过的值。

1
2
3
4
5
6
7
8
9
10
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));

鼓励我一下:

觉得还不错的话,给我的点个star

听说,打赏我的人最后都找到了真爱。