JS求解两数之和算法详解

本文实例讲述了JS求解两数之和算法。分享给大家供大家参考,具体如下:

题目描述

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

::: tip
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
:::

解法

利用 Map 记录数组元素值和对应的下标,对于一个数 nums[i],判断 target - nums[i] 是否存在 Map

var twoSum = function(nums, target) {
 const _length = nums.length;
 const _mayMap = new Map();
 for (let i = 0; i < _length; i++) {
 if (_mayMap.has(target - nums[i])) {
  return [_mayMap.get(target - nums[i]), i];
 }
 _mayMap.set(nums[i], i);
 }
};

Map回顾

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

new Map([iterable])

Iterable 可以是一个数组或者其他 iterable 对象,其元素为键值对(两个元素的数组,例如:[[ 1, 'one' ],[ 2, 'two' ]])。 每个键值对都会添加到新的 Mapnull 会被当做 undefined

Objects 和 maps 的比较

ObjectsMaps 类似的是,它们都允许你按键存取一个值、删除键、检测一个键是否绑定了值。

因此(并且也没有其他内建的替代方式了)过去我们一直都把对象当成 Maps 使用。

不过 MapsObjects 有一些重要的区别,在下列情况里使用 Map 会是更好的选择:

一个Object的键只能是字符串或者 Symbols,但一个 Map 的键可以是任意值,包括函数、对象、基本类型。

Map 中的键值是有序的,而添加到对象中的键则不是。因此,当对它进行遍历时,Map 对象是按插入的顺序返回键值。

可以通过 size 属性直接获取一个Map的键值对个数,而 Object的键值对个数只能手动计算。

Map 可直接进行迭代,而 Object 的迭代需要先获取它的键数组,然后再进行迭代。

Object 都有自己的原型,原型链上的键名有可能和你自己在对象上的设置的键名产生冲突。
虽然 ES5 开始可以用 map = Object.create(null) 来创建一个没有原型的对象,但是这种用法不太常见。

Map 在涉及频繁增删键值对的场景下会有些性能优势。

属性

Map.length
属性 length 的值为 0 。

get Map[@@species]
本构造函数用于创建派生对象。

Map.prototype
表示 Map 构造器的原型。 允许添加属性从而应用于所有的 Map 对象。

所有的 Map 对象实例都会继承 Map.prototype。

Map.prototype.constructor
返回一个函数,它创建了实例的原型。默认是Map函数。

Map.prototype.size
返回Map对象的键/值对的数量。

Map.prototype.clear()
移除Map对象的所有键/值对 。

Map.prototype.delete(key)
如果 Map 对象中存在该元素,则移除它并返回 true;否则如果该元素不存在则返回 false

Map.prototype.entries()
返回一个新的 Iterator 对象,它按插入顺序包含了Map对象中每个元素的 [key, value] 数组。

Map.prototype.forEach(callbackFn[, thisArg])
按插入顺序,为 Map对象里的每一键值对调用一次callbackFn函数。如果为forEach提供了thisArg,它将在每次回调中作为this值。

Map.prototype.get(key)
返回键对应的值,如果不存在,则返回undefined。

Map.prototype.has(key)
返回一个布尔值,表示Map实例是否包含键对应的值。

Map.prototype.keys()
返回一个新的 Iterator对象, 它按插入顺序包含了Map对象中每个元素的键 。

Map.prototype.set(key, value)
设置Map对象中键的值。返回该Map对象。

Map.prototype.values()
返回一个新的Iterator对象,它按插入顺序包含了Map对象中每个元素的值 。

Map.prototype[@@iterator]()
返回一个新的Iterator对象,它按插入顺序包含了Map对象中每个元素的 [key, value] 数组。

例子

var myMap = new Map();

var keyObj = {},
 keyFunc = function () {},
 keyString = "a string";

// 添加键
myMap.set(keyString, "和键'a string'关联的值");
myMap.set(keyObj, "和键keyObj关联的值");
myMap.set(keyFunc, "和键keyFunc关联的值");

myMap.size; // 3

// 读取值
myMap.get(keyString); // "和键'a string'关联的值"
myMap.get(keyObj);  // "和键keyObj关联的值"
myMap.get(keyFunc);  // "和键keyFunc关联的值"

myMap.get("a string"); // "和键'a string'关联的值"
       // 因为keyString === 'a string'
myMap.get({});   // undefined, 因为keyObj !== {}
myMap.get(function() {}) // undefined, 因为keyFunc !== function () {}

传递数据

let valuesMap = new Map();

class payserviceclass {
 constructor() {}
 getItem(key) {
 const stringKey = String(key);
 if (valuesMap.has(key)) {
  return valuesMap.get(stringKey);
 }
 return null;
 }
 setItem(key, val) {
 return valuesMap.set(String(key), val);
 }

 clear() {
 return valuesMap.clear();
 }
}
const payservice = new payserviceclass();

export default payservice;

参考:
https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Map

感兴趣的朋友可以使用在线HTML/CSS/JavaScript代码运行工具:http://tools.jb51.net/code/HtmlJsRun测试上述代码运行效果。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

时间: 2020-04-27

JS使用Prim算法和Kruskal算法实现最小生成树

之前都是看书,大部分也是c++的实现,但是搞前端不能忘了JS啊,所以JS实现一遍这两个经典的最小生成树算法. 一.权重图和最小生成树 权重图:图的边带权重 最小生成树:在连通图的所有生成树中,所有边的权重和最小的生成树 本文使用的图如下: 它的最小生成树如下: 二.邻接矩阵 邻接矩阵:用来表示图的矩阵就是邻接矩阵,其中下标表示顶点,矩阵中的值表示边的权重(或者有无边,方向等). 本文在构建邻接矩阵时,默认Number.MAX_SAFE_INTEGER表示两个节点之间没有边,Number.MIN_

JavaScript求一组数的最小公倍数和最大公约数常用算法详解【面向对象,回归迭代和循环】

本文实例讲述了JavaScript求一组数的最小公倍数和最大公约数常用算法.分享给大家供大家参考,具体如下: 方法来自求多个数最小公倍数的一种变换算法(详见附录说明) 最小公倍数的算法由最大公约数转化而来.最大公约数可通过如下步骤求得: (1) 找到a1,a2,..,an中的最小非零项aj,若有多个最小非零项则任取一个 (2) aj以外的所有其他非0项ak用ak mod aj代替:若没有除aj以外的其他非0项,则转到(4) (3) 转到(1) (4) a1,a2,..,an的最大公约数为aj 写

javascript算法题 求任意一个1-9位不重复的N位数在该组合中的大小排列序号

具体题目是这样的: 从1--9中选取N个数字,组成不重复的N位数,从小到大进行编号,当输入其中任何一个数M时,能找出该数字对应 的编号.如 N=3,M=213. 输出:[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]--->X=2 首先看到题目想到的是生成一个从少到大的全排列的数组,然后再遍历数组得到对应的序号(数组下标加1),又或者想到一个个从小到大的生成push进数组,然后判断该数是不是当前题目给的数,如果是的话要求的序号就是当前数组

JavaScript实现的一个计算数字步数的算法分享

这两天看了下某位大神的github,知道他对算法比较感兴趣,看了其中的一个计算数字的步数算法,感觉这个有点意思,所以就自己实现了一个. 算法描述与实现原理 给出一个整型数字,统计出有多少种走法可以到达目标,比如一个数字4,可以有下面几种走法 复制代码 代码如下: [ 1, 3 ]         [ 4 ]     [ 1, 1, 2 ]         [ 2, 2 ]     [ 1, 1, 1, 1 ] 其实通过上面的组合可以得出下面的结论. 1.先列出所有项是1的组合 2.依次从左到右项

javascript使用递归算法求两个数字组合功能示例

本文实例讲述了javascript使用递归算法求两个数字组合功能.分享给大家供大家参考,具体如下: // 12 ,3,4 两个数字组合 最后结果 应该是 // 13 // 14 // 23 // 24 // 34 // 这5种 用程序 怎么算出来 // 是求组合的算法 // var arr = [12, 3, 4]; // var len = arr.length; // var result = []; // for (var i = 0; i < len; i++) { // for (va

JavaScript采用递归算法计算阶乘实例

本文实例讲述了JavaScript采用递归算法计算阶乘的方法.分享给大家供大家参考.具体如下: 这里使用JavaScript中的递归算法计算阶乘,初学编程时候,这是很常见的小例子,比较一下,JS中的计算方法与其有何异同. 运行效果如下: 具体代码如下: <html> <head> <meta http-equiv="content-type" content="text/html; charset=GB2312" /> <t

JS使用Dijkstra算法求解最短路径

一.Dijkstra算法的思路 Dijkstra算法是针对单源点求最短路径的算法. 其主要思路如下: 1. 将顶点分为两部分:已经知道当前最短路径的顶点集合Q和无法到达顶点集合R. 2. 定义一个距离数组(distance)记录源点到各顶点的距离,下标表示顶点,元素值为距离.源点(start)到自身的距离为0,源点无法到达的顶点的距离就是一个大数(比如Infinity). 3. 以距离数组中值为非Infinity的顶点V为中转跳点,假设V跳转至顶点W的距离加上顶点V至源点的距离还小于顶点W至源点

javascript算法题:求任意一个1-9位不重复的N位数在该组合中的大小排列序号

具体题目是这样的: 从1--9中选取N个数字,组成不重复的N位数,从小到大进行编号,当输入其中任何一个数M时,能找出该数字对应 的编号.如 N=3,M=213.     输出:[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]--->X=2 首先看到题目想到的是生成一个从少到大的全排列的数组,然后再遍历数组得到对应的序号(数组下标加1),又或者想到一个个从小到大的生成push进数组,然后判断该数是不是当前题目给的数,如果是的话要求的序号就是

JS实现计算小于非负数n的素数的数量算法示例

本文实例讲述了JS实现计算小于非负数n的素数的数量算法.分享给大家供大家参考,具体如下: 计算小于非负数n的素数的数量 例: 输入: 10 输出: 4 说明:有4个素数小于10,它们是2,3,5,7. JS算法示例: <script> var countPrimes = function(n) { let flagArray = [], result = 0; for(let i = 2; i < n; i++){ if(flagArray[i] === undefined){ flag

JavaScript实现数组全排列、去重及求最大值算法示例

本文实例讲述了JavaScript实现数组全排列.去重及求最大值算法.分享给大家供大家参考,具体如下: 1.全排列(递归) function permutation(arr){ if (arr.length == 1) return arr; else if (arr.length == 2) return [[arr[0],arr[1]],[arr[1],arr[0]]]; else { var temp = []; for (var i = 0; i < arr.length; i++) {

javascript中解析四则运算表达式的算法和示例

在编写代码时我们有时候会碰到需要自己解析四则运算表达式的情况,本文简单的介绍使用JavaScript实现对简单四则运算表达式的解析. 一.熟悉概念 中缀表示法(或中缀记法)是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4).也就是我们最常用的算术表达式,中缀表达式对于人类来说比较容易理解,但是不易于计算机解析. 逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式

详解JavaScript中操作符和表达式

一.一元操作符 1.delete操作符 delete 操作符用于删除对象的某个属性:如果没有指向这个属性的引用,那它最终会被释放 语法:delete expression delete 操作符会从某个对象上移除指定属性.成功删除的时候回返回 true,否则返回 false let Employee = { age: 28, name: 'abc', designation: 'developer' }; console.log(delete Employee.name); // returns

JavaScript中自带的 reduce()方法使用示例详解

1.方法说明 , Array的reduce()把一个函数作用在这个Array的[x1, x2, x3...]上,这个函数必须接收两个参数,reduce()把结果继续和序列的下一个元素做累积计算,其效果就是: [x1, x2, x3, x4].reduce(f) = f(f(f(x1, x2), x3), x4) 2. 使用示例 'use strict'; function string2int(s){ if(!s){ alert('the params empty'); return; } if

JavaScript中的ajax功能的概念和示例详解

AJAX即"Asynchronous Javascript And XML"(异步JavaScript和XML). 个人理解:ajax就是无刷新提交,然后得到返回内容. 对应的不使用ajax时的传统网页如果需要更新内容(或用php做处理时),必须重载整个网页页面. 示例: html代码如下 <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>

JavaScript中reduce()的5个基本用法示例

前言 reduce()方法可以搞定的东西,for循环,或者forEach方法有时候也可以搞定,那为啥要用reduce()?这个问题,之前我也想过,要说原因还真找不到,唯一能找到的是:通往成功的道路有很多,但是总有一条路是最捷径的,亦或许reduce()逼格更高... 语法 arr.reduce(callback,[initialValue]) reduce()方法对数组中的每一个元素执行一个reducer函数(由你提供),从而得到一个单一的输出值. reduce() 方法将一个数组中的所有元素还

JavaScript 中判断变量是否为数字的示例代码

简介 JavaScript 是一种动态类型语言,这意味着解释器在运行时确定变量的类型.实际上,这也允许我们在相同的代码中使用相同的变量来存储不同类型的数据.如果没有文档和一致性,我们在使用代码时并不总是知道变量的类型. 当我们期望一个变量是数字时,对字符串或数组进行操作可能会在代码中导致奇怪的结果.在本文中,我们将会介绍一些判断变量是否为数字的函数. 像"10"之类的数字的字符串不应被接受.在JavaScript中,诸如NaN,Infinity和-Infinity之类的特殊值也是数字类

理解 javascript 中的函数表达式与函数声明

常用闭包的同学肯定很清楚下面一段代码: //通常的闭包写法 (function () { ... }()) 那么我们的问题来了,为什么要在 function () {...}() 之外用圆括号包裹呢?解答这个问题,就需要我们理解 Javascript 中函数表达式与函数声明的概念. 函数定义带来的错误 虽然 function () {...} 看上去像是一个函数声明,但是由于没有函数名,它的本质其实是一个函数表达式.我们看下规范中对于函数声明与函数表达式的定义: 可以看出来,函数声明是必须带有函

JavaScript中运算符规则和隐式类型转换示例详解

前言 本文主要给大家介绍了关于JavaScript运算符规则和隐式类型转换的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 隐式类型转换 在 JavaScript 中,当我们进行比较操作或者加减乘除四则运算操作时,常常会触发 JavaScript 的隐式类型转换机制:而这部分也往往是令人迷惑的地方.譬如浏览器中的 console.log 操作常常会将任何值都转化为字符串然后展示,而数学运算则会首先将值转化为数值类型(除了 Date 类型对象)然后进行操作. 我们首先来

JavaScript中的垃圾回收与内存泄漏示例详解

前言 程序的运行需要内存.只要程序提出要求,操作系统或者运行时就必须供给内存.所谓的内存泄漏简单来说是不再用到的内存,没有及时释放.为了更好避免内存泄漏,我们先介绍Javascript垃圾回收机制. 在C与C++等语言中,开发人员可以直接控制内存的申请和回收.但是在Java.C#.JavaScript语言中,变量的内存空间的申请和释放都由程序自己处理,开发人员不需要关心.也就是说Javascript具有自动垃圾回收机制(Garbage Collecation). 一.垃圾回收的必要性 下面这段话

Javascript中eval函数的使用方法与示例

定义和用法 eval() 函数可计算某个字符串,并执行其中的的 JavaScript 代码. 语法 eval(string) 参数 描述 string 必需.要计算的字符串,其中含有要计算的 JavaScript 表达式或要执行的语句. 返回值 通过计算 string 得到的值(如果有的话). 说明 该方法只接受原始字符串作为参数,如果 string 参数不是原始字符串,那么该方法将不作任何改变地返回.因此请不要为 eval() 函数传递 String 对象来作为参数. 如果试图覆盖 eval