内容简介: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
破解了这道题。
不折腾的前端,和咸鱼有什么区别!
jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。
扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 算法题:两数之和
- LeetCode-1-两数之和
- Leetcode 1:两数之和
- LeetCode题解 - 1. 两数之和
- LeetCode 第 1 号问题:两数之和
- LeetCode 1:两数之和 Two Sum
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
PCI Express 体系结构导读
王齐 / 机械工业 / 2010-3 / 55.00元
《PCI Express 体系结构导读》讲述了与PCI及PCI Express总线相关的最为基础的内容,并介绍了一些必要的、与PCI总线相关的处理器体系结构知识,这也是《PCI Express 体系结构导读》的重点所在。深入理解处理器体系结构是理解PCI与PCI Express总线的重要基础。 读者通过对《PCI Express 体系结构导读》的学习,可超越PCI与PCI Express总线......一起来看看 《PCI Express 体系结构导读》 这本书的介绍吧!