两数之和

难度:简单

描述:

给一个整数数组,找到两个数使得他们的和等于一个给定的数 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

想一想再看答案

想一想再看答案

想一想再看答案

代码:

  1. 转成对象:

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

/**
 * @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
  1. 双循环
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
  1. 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

鼓励我一下:

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

Last Updated: 10/24/2018, 8:07:31 PM