欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JS求解两数之和算法详解

程序员文章站 2022-04-25 17:38:57
本文实例讲述了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

objectsmaps 的比较

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测试上述代码运行效果。