算法_两数之和

两数之和

难度：简单

描述：

给一个整数数组，找到两个数使得他们的和等于一个给定的数 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. 转成对象：

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

/**
 * @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));

2. 双循环

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));

3. 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));

鼓励我一下：

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