LeetCode - 167 - 两数之和II（two-sum-ii-input-array-is-sorted）

栏目: IT技术 · 发布时间: 5年前

内容简介：LeetCode - 167 - 两数之和II（two-sum-ii-input-array-is-sorted）

Create by jsliang on 2019-07-04 17:17:39
Recently revised in 2019-07-04 19:08:39

一目录

不折腾的前端，和咸鱼有什么区别

| 目录 | | --- | | 一目录 | | 二前言 | | 三解题 | | 3.1 解法 - 双指针 | | 3.2 解法 - Map() |

二前言

难度：简单
涉及知识：数组、双指针、二分查找
题目地址：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
题目内容：

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

三解题

小伙伴可以先自己在本地尝试解题，再回来看看 jsliang 的解题思路。

3.1 解法 - 双指针

解题代码：

var twoSum = function(numbers, target) {
  for (let i = 0; i < numbers.length - 1; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] === target) {
        return [i + 1, j + 1];
      }
    }
  }
  return [];
};

执行测试：

numbers： [2,7,11,15]
target： 9
return： [1,2]

LeetCode Submit：

✔ Accepted
  ✔ 17/17 cases passed (436 ms)
  ✔ Your runtime beats 13.64 % of javascript submissions
  ✔ Your memory usage beats 94.19 % of javascript submissions (34.6 MB)

解题思路：

拿到题，看下题目，想 1 分钟思路，敲 1 分钟代码，提交，完事……

我变强了，还好没那么快秃！

首先，想到的就是双指针法，思路很简单：

当 i 遍历到 2 的时候， j 依次遍历 7、 11、 15
当 i 遍历到 7 的时候， j 依次遍历 11、 15
当 i 遍历到 11 的时候， j 依次遍历 15
当 i 为 15 的时候，不遍历。

当然，这是正常情况下， i 指针和 j 指针指向不同的位置。

然后：

if (numbers[i] + numbers[j] === target) {
  return [i + 1, j + 1];
}

判断这两者相加是否为 target 的值，相同则 return 出去就行了。

最后，如果小伙伴们还是没看懂这解题思路，建议多看两道双指针的题目，原理都是十分简单的。

3.2 解法 - Map()

解题代码：

var twoSum = function(numbers, target) {
  let map = new Map();
  for (let i = 0; i < numbers.length; i++) {
    if (map.get(numbers[i]) !== undefined) {
      return [map.get(numbers[i]), i + 1];
    } else {
      map.set(target - numbers[i], i + 1);
    }
  }
  return [];
};

执行测试：

numbers： [2,7,11,15]
target： 9
return： [1,2]

LeetCode Submit：

✔ Accepted
  ✔ 17/17 cases passed (68 ms)
  ✔ Your runtime beats 98.53 % of javascript submissions
  ✔ Your memory usage beats 6.77 % of javascript submissions (35.5 MB)

知识点：

Map：保存键值对。任何值(对象或者原始值) 都可以作为一个键或一个值。 Map 详细介绍

解题思路：

回头想了一下，杀它个回马枪

在双指针解法中，我们花费了大量的时间，因为进行了双重 for 遍历。

那么，我们可不可以压缩下呢？

于是，咱想到了 Map，使用哈希算法来解题。

让我们看看，将遍历中的数据，都进行 Map 存储，是怎样子的：

Map { 7 => 0 }
undefined
Map { 7 => 0, 2 => 1 }
0
Map { 7 => 0, 2 => 1, -2 => 2 }
undefined
Map { 7 => 0, 2 => 1, -2 => 2, -6 => 3 }
undefined

看到这里，小伙伴们心里是不是异常清晰了？

是的，我们将每个数字的差值，作为 key 存储起来，然后将每个数字的索引（ index），作为 value 存储起来。

这样，当我们获取不存在的值的时候，返回 undefined；

获取 9-2=7 的时候，它就不是 undefined 了，而是告诉我们它的 value 为 0

最终，通过判断取到的 value 是否为 undefined，我们成功通过 Map 破解了这道题。

不折腾的前端，和咸鱼有什么区别！

LeetCode - 167 - 两数之和II（two-sum-ii-input-array-is-sorted）

jsliang 会每天更新一道 LeetCode 题解，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构。

扫描上方二维码，关注 jsliang 的公众号，让我们一起折腾！

jsliang 的文档库由梁峻荣采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。