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/

  • 题目内容

  1. 给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

  2. 函数应该返回这两个下标值 index1 index2,其中 index1 必须小于 index2

  3. 说明:

  4. 返回的下标值(index1 index2)不是从零开始的。

  5. 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

  6. 示例:

  7. 输入: numbers = [2, 7, 11, 15], target = 9

  8. 输出: [1,2]

  9. 解释: 2 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2

三 解题

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

3.1 解法 - 双指针

  • 解题代码

  1. var twoSum = function(numbers, target) {

  2. for (let i = 0; i < numbers.length - 1; i++) {

  3. for (let j = i + 1; j < numbers.length; j++) {

  4. if (numbers[i] + numbers[j] === target) {

  5. return [i + 1, j + 1];

  6. }

  7. }

  8. }

  9. return [];

  10. };

  • 执行测试

  1. numbers: [2,7,11,15]

  2. target: 9

  3. return: [1,2]

  • LeetCode Submit

  1. Accepted

  2. 17/17 cases passed (436 ms)

  3. Your runtime beats 13.64 % of javascript submissions

  4. Your memory usage beats 94.19 % of javascript submissions (34.6 MB)

  • 解题思路

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

我变强了,还好没那么快秃!

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

  1. 当 i 遍历到 2 的时候, j 依次遍历 7、 11、 15

  2. 当 i 遍历到 7 的时候, j 依次遍历 11、 15

  3. 当 i 遍历到 11 的时候, j 依次遍历 15

  4. 当 i 为 15 的时候,不遍历。

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

然后

  1. if (numbers[i] + numbers[j] === target) {

  2. return [i + 1, j + 1];

  3. }

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

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

3.2 解法 - Map()

  • 解题代码

  1. var twoSum = function(numbers, target) {

  2. let map = new Map();

  3. for (let i = 0; i < numbers.length; i++) {

  4. if (map.get(numbers[i]) !== undefined) {

  5. return [map.get(numbers[i]), i + 1];

  6. } else {

  7. map.set(target - numbers[i], i + 1);

  8. }

  9. }

  10. return [];

  11. };

  • 执行测试

  1. numbers: [2,7,11,15]

  2. target: 9

  3. return: [1,2]

  • LeetCode Submit

  1. Accepted

  2. 17/17 cases passed (68 ms)

  3. Your runtime beats 98.53 % of javascript submissions

  4. Your memory usage beats 6.77 % of javascript submissions (35.5 MB)

  • 知识点

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

  • 解题思路

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

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

那么,我们可不可以压缩下呢?

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

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

  1. Map { 7 => 0 }

  2. undefined

  3. Map { 7 => 0, 2 => 1 }

  4. 0

  5. Map { 7 => 0, 2 => 1, -2 => 2 }

  6. undefined

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

  8. undefined

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

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

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

获取 9-2=7 的时候,它就不是 undefined 了,而是告诉我们它的 value0

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


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

LeetCode - 167 - 两数之和II(two-sum-ii-input-array-is-sorted)

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

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

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


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

面向对象葵花宝典:思想、技巧与实践

面向对象葵花宝典:思想、技巧与实践

李运华 编著 / 电子工业出版社 / 2015-12 / 69

《面向对象葵花宝典:思想、技巧与实践》系统地讲述了面向对象技术的相关内容,包括面向对象的基本概念、面向对象开发的流程、面向对象的各种技巧,以及如何应用面向对象思想进行架构设计。在讲述相关知识或技术的时候,除了从“是什么”这个角度进行介绍外,更加着重于从“为什么”和“如何用”这两个角度进行剖析,力争让读者做到“知其然,并知其所以然”,从而达到在实践中既能正确又能优秀地应用面向对象的相关技术和技巧。 ......一起来看看 《面向对象葵花宝典:思想、技巧与实践》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具