二和 Leetcode 解释、Hashmap、Javascript

2024-04-24

我只是想知道谁能一步一步解释这个解决方案的算法。我不知道哈希图是如何工作的。您能否还提供一个使用哈希图的基本示例,以便我理解该算法。谢谢你!

var twoSum = function(nums, target) {
  let hash = {};

  for(let i = 0; i < nums.length; i++) {
    const n = nums[i];
    if(hash[target - n] !== undefined) {
      return [hash[target - n], i];
    }
    hash[n] = i;
  }
  return [];
}

您的代码需要一个数字数组和一个目标数字/总和。然后,它返回数组中两个数字的索引,这两个数字的总和达到目标数字/总和。

考虑一个数字数组,例如[1, 2, 3]和一个目标5。你的任务是找到这个数组中的两个数字,将其相加5。解决这个问题的一种方法是循环遍历数组中的每个数字并问自己“是否有一个数字(我已经在数组中看到过),我可以将其添加到当前数字中以获得我的值”target sum?".

好吧,如果我们循环示例数组[1, 2, 3]我们首先从索引 0 开始,编号为1。目前,我们还没有看到可以添加的数字1达到我们的目标5因为我们还没有循环任何数字。

所以,到目前为止,我们已经遇到了这个数字1,位于索引处0。这存储在哈希图(即对象)中:{'1': 0}。其中键是数字和值 (0) 是它被看到的索引。该对象的目的是存储我们看到的数字以及它们出现的索引。

接下来,继续循环到索引 1,当前编号为2。现在我们可以问自己一个问题:是否有一个我已经在数组中看到的数字可以添加到我当前的数字中2得到目标总和5。可以通过以下方式获得达到目标所需添加到当前数字的金额target-currentNumber。在这种情况下,我们目前正在2,所以我们需要添加3达到我们的目标总和 5。使用 hashmap/object,我们可以检查我们是否已经看到了这个数字3。为此,我们可以尝试访问该对象3关键是做obj[target-currentNumber]。目前,我们的对象只有以下键'1',所以当我们尝试访问3你会得到的钥匙undefined。这意味着我们还没有看到这个数字3然而,到目前为止,我们还没有什么可以添加的2得到我们的target sum.

所以现在我们的对象/哈希图看起来像{'1': 0, '2': 1},正如我们看到的数字1位于索引处0,我们已经看到了这个数字2位于索引处1.

最后,我们到达数组中位于索引 2 处的最后一个数字。数组的索引 2 保存该数字3。现在,我们再次问自己这个问题:是否有一个我们已经看到的数字可以添加到其中3(我们当前的号码)以获得target和?。我们需要添加的号码3以获得我们的目标数量5 is 2(通过做得到target-currentNumber)。我们现在可以检查我们的对象,看看我们是否已经看到了一个数字2在数组中。为此,我们可以使用obj[target-currentNumber]获取存储在键中的值2,它存储索引 1。这意味着数字2数组中确实存在,因此我们可以将其添加到3达到我们的目标。由于该值位于对象中,因此我们现在可以返回我们的发现。这是所见数字发生位置的索引,以及当前数字的索引。

一般来说,该对象用于跟踪数组中所有先前看到的数字,并保留看到该数字的索引值。

这是运行代码的示例。它返回[1, 2],作为索引处的数字1 and 2可以相加得到目标总和5:

const twoSum = function(nums, target) {
  const hash = {}; // Stores seen numbers: {seenNumber: indexItOccurred}

  for (let i = 0; i < nums.length; i++) { // loop through all numbers
    const n = nums[i]; // grab the current number `n`.
    if (hash[target - n] !== undefined) { // check if the number we need to add to `n` to reach our target has been seen:
      return [hash[target - n], i]; // grab the index of the seen number, and the index of the current number
    }
    hash[n] = i; // update our hash to include the. number we just saw along with its index.
  }
  return []; // If no numbers add up to equal the `target`, we can return an empty array
}

console.log(twoSum([1, 2, 3], 5)); // [1, 2]

A solution like this might seem over-engineered. You might be wondering why you can't just look at one number in the array, and then look at all the other numbers and see if you come across a number that adds up to equal the target. A solution like that would work perfectly fine, however, it's not very efficient. If you had N numbers in your array, in the worst case (where no two numbers add up to equal your target) you would need to loop through all of these N numbers - that means you would do N iterations. However, for each iteration where you look at a singular number, you would then need to look at each other number using a inner loop. This would mean that for each iteration of your outer loop you would do N iterations of your inner loop. This would result in you doing N*N or N2 work (O(N2) work). Unlike this approach, the solution described in the first half of this answer only needs to do N iterations over the entire array. Using the object, we can find whether or not a number is in the object in constant (O(1)) time, which means that the total work for the above algorithm is only O(N).

有关对象如何工作的更多信息,您可以阅读括号表示法和其他属性访问器方法here https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Property_accessors#Bracket_notation.

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

二和 Leetcode 解释、Hashmap、Javascript 的相关文章

  • 突出显示 Html 文档中不同标签的文本

    我是新来的角js 现在我正在突出显示 HTML 文档中的文本 So 我的代码是这样的 var InstantSearch highlight function container highlightText var internalHigh
  • 修复 JSLint“意外的‘this’。”错误?

    我试图让以下代码成为符合 jslint 标准 http jslint com 但我陷入以下两个错误 本来应该看到一个声明 结果却看到了一个块 and 意想不到的 这个 我应该对我的代码进行哪些更改才能使 JSLint 满意 var pvAc
  • D3.js分组条形图

    I am making a bar chart using D3 js like this source statcan gc ca http www statcan gc ca pub 12 593 x 2007001 figures f
  • 无法实现模块模式

    我正在尝试重现 Douglas Crockford 所著的 Javascript The Good Parts 一书中的一些代码 这个想法是使用闭包进行对象封装并避免Javascript固有的全局变量 var serial maker fu
  • 没有函数或 json 的 JavaScript 大括号

    刚刚打开客户端的 javascript 文件 第一行是这样的 var s account blog 我不明白 通常 根据我的经验 花括号包裹着一个函数 function welcome or a json JavaScript object
  • Angular JS - 提交到 $http 时日期发生变化 - 时区问题

    我遇到一个奇怪的问题Date当它通过 http put 传递到 API 时发生变化 我怀疑时区问题 Datepicker 触发 ng change 事件 console log Tue Jun 10 2014 00 00 00 GMT 01
  • 在网页上写乐谱[关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 我希望能够在网页中编写乐谱和和弦 有没有可用的库 例如用于数学的 Mathjax 如果没有 那么还有其
  • jQuery 无法在外部 JavaScript 中工作

    我是 jQuery 新手 遇到了一些奇怪的问题 我正在使用 jQuery 的change and click方法 在我的 HTML 文件中使用时它们工作正常
  • JavaScript 对象镜像/单向属性同步

    出于安全目的 我需要一个 镜像 对象 也就是说 如果我创建对象 A 并浅克隆 A 的副本并将其称为 B 则每当 A 的属性发生更改时 我希望 B 自动更新自身以反映更改 但反之则不然 换句话说 单向属性同步 我的问题 是否已经存在我不知道的
  • 在气球内显示带有照片的多个地标的最佳做法是什么?

    我有一个项目如下 从手机上拍摄几张照片 将照片保存在网络系统中 然后将照片显示在其中的谷歌地球上 我读过很多文章 但它们都使用 fetchKml 我读过的一篇好文章是使用 php 但使用 fetchKml 我不知道是否可以使用 parseK
  • Android 上的 Chrome 强制隐藏地址栏

    我最近开发了一个获取混合 http https 内容的网站 因此 我总是将地址栏显示在顶部 它不会像其他网站那样自动隐藏 这就是我要说的 This https planetkde org 是网站的链接 内容是从各种来源获取的 因此无法过滤非
  • 定时器内嵌套异步等待 - 不返回所需的值

    我必须使用 Mocha 和 chai 测试来测试端点的响应 下面是相同的代码 async function getData userId let response let interval setInterval async gt resp
  • 检测 iPad Safari 用户的最佳方法

    添加用于检测 iPad Safari 用户的代码的最佳方法是什么 我的意思是我们应该使用 1 CSS 通过链接媒体 2 JS 通过navigator对象 我听说使用用户代理字符串并不是检测 iPad 的最佳方法 因为存在不一致的情况 请建议
  • 无法安装js-bson

    我正在使用Windows 7 64位 尝试安装bson作为mongodb的依赖项 我收到此错误 npm WARN package json email protected cdn cgi l email protection No READ
  • 什么是闭包编译器?

    如果您不知道我在说什么 请查看以下内容 http closure compiler appspot com home http closure compiler appspot com home 这是一个 JavaScript 压缩器 在他
  • 将罗马数字转换为阿拉伯数字--recursiv

    我是 JavaScript 新手 正在网站的帮助下学习https www jshero net koans roman1 html https www jshero net koans roman1 html 本练习是编写一个转换器 将罗马
  • 如何使用 Javascript 从 Chrome iOS 下载 blob 文件?

    如何使用 Javascript 从 Chrome iOS 下载 blob 文件 我正在从 iOS 下载文件 pdf excel txt png iOS 没有文件系统 这对下载来说是一个问题 我创建了一个代码 根据操作系统和导航器 如果需要
  • 让管道自我刷新角度

    我有来自后端的静态时间戳 我想每 1 秒刷新一次管道以获取现在的日期 这是我的烟斗 import Pipe PipeTransform from angular core import moment from moment Pipe nam
  • IE 中带有“删除”方法的 jQuery.ajax 问题

    我有一个页面 用户可以使用按钮编辑各种内容并选择触发 ajax 调用 特别是 一个操作会导致远程调用一个 url 其中包含一些数据和 放置 请求 这 因为我使用的是宁静的 Rails 后端 会触发我的更新操作 我还有一个删除按钮 它调用相同
  • 如果列表在初始化之前为空,则 jQuery 可排序无法与水平列表正常工作

    如果我在初始化后将元素添加到列表中 sortable它无法正常工作 参见示例jsFiddle http jsfiddle net NQMPr 1 示例 HTML div class container div br

随机推荐

  • SEO 友好的 URL 真的会影响页面的排名吗? [关闭]

    Closed 这个问题不符合堆栈溢出指南 help closed questions 目前不接受答案 如今 SEO 友好的 URL 非常流行 但它们实际上对 Google 和其他搜索引擎中的页面排名产生有意义的影响吗 如果是这样 为什么 如
  • 稳定标准库 qsort?

    我假设 stdlib 中的旧 qsort 函数不稳定 因为手册页没有提及任何相关内容 这就是我正在谈论的功能 include
  • 部署的 Django 项目出现“列表索引超出范围”错误。本地项目工程

    我的项目在本地计算机上运行正常 但是当我将其部署到服务器时出现错误 异常值 列表索引超出范围 异常位置 get context data中的 var www bias experiment src survey views py 第151行
  • MessageBox.Show() 字体

    有没有办法可以更改 MessageBox Show 中的字体类型以获得更大的尺寸 粗体 斜体样式 您始终可以创建自己的 MessageBox 创建一个新的 Windows Forms 类 using System using System
  • scanf函数返回什么?

    scanf 在以下情况下返回的值是多少 int g int p scanf d g Originally int p scanf d g 我知道签名scanf函数是 int scanf const char format 是什么int该函数
  • 使用带有百分比的 CSS Clip

    我试图在 2 个单独的 div 中仅显示图像的上半部分和同一图像的下半部分 我尝试过使用 CSS 属性clip 但似乎不支持 作为单位 只有我吗 您有只显示一半图像的解决方案吗 更新 5年以上后 CSS Clip 属性现已弃用 考虑使用cl
  • 在远程机器上执行多个命令

    在下面的命令中 我尝试 ssh 命令并执行多个命令 如果任何命令失败 即如果 command1 退出 那么如果 command1 和 commnd 2 退出 否则在远程计算机上执行命令 3 我如何退出 我怎样才能做到这一点 ssh logi
  • 如何使用 Laravel 将二进制数据插入数据库?

    我正在尝试使用 Laravel 4 及其 Eloquent ORM 将二进制数据插入到 PostgreSQL 数据库中 我在迁移中有以下内容 Schema create DataBlobs function table table gt i
  • 如何获取驱动器号和名称(卷标)

    我有一个程序可以告诉我所有硬盘 USB 但它只告诉我驱动器号而不是名称 这是我所拥有的 DriveInfo drives DriveInfo GetDrives Console WriteLine Detected Drives for i
  • 计算一个月的工作日数[重复]

    这个问题在这里已经有答案了 可能的重复 获取给定月份的工作日数 https stackoverflow com questions 8396507 get number of weekdays in a given month 如何计算每个
  • 如何在Android中从url获取字节图像

    我是 android 新手 图像存储在服务器中Base64格式 那么我怎样才能得到它server to 我的项目并使用 Json 对象设置为我的 ImageView 请帮我 任何帮助将不胜感激 尝试这个 首先将 Url 转换为 byte b
  • Django:如何在ajax中返回模型表单集并在模板中使用

    我需要在运行时使用ajax动态地将表单添加到我的表单集中 我指的是使用 Ajax 将表单动态添加到 Django 表单集 https stackoverflow com questions 501719 dynamically adding
  • 为什么 Android webview 仅当 type="number" 而不是 type="text" 时才在键盘中显示“下一步”?

    我有一个带有几个输入字段的表单 因此 我想使用下一个按钮在字段之间导航 但这仅在输入字段类型为 数字 时有效 使用 type text 则不会 这是 Android 3 2 1 中的错误吗 我的输入字段是这样的
  • WPF Datagrid - 如何验证多行并标记所有无效行?

    我有一个包含行的数据网格 其中验证取决于他的兄弟姐妹 到目前为止 我正在使用 BindingGroups 和自定义 ValidationRule 同时验证多行 但我不知道如何更改无效行条目的外观 我返回一个 ValidationResult
  • NSView mouseEntered/mouseMoved 在拖动操作期间未调用(反之亦然)

    我有一个带有透明边框的无边框窗口NSView 当鼠标光标进入透明视图时 应该会出现第二个视图 放置目标 允许用户放置文件 问题是draggingEntered 将文件拖到上方时不会被调用透明视图 因此放置目标视图永远不会出现 透明视图具有正
  • 如何使图像在轮播中居中

    如何使图像在轮播中居中 我使用 bootstrap 教程中的代码尝试了 bootstrap 3 carousel a href Webconte Details 124 img src Webconte Image 124 a div cl
  • R 中函数多态性的建议做法是什么?

    假设我想写一个函数R这是对某些数据进行充分统计的函数 例如 假设函数 调用它foo func仅取决于数据样本的样本均值 为了方便起见 我认为用户可能喜欢传递到foo func随机变量的样本 在这种情况下foo func计算样本平均值 or样
  • ZeroMQ,我们可以使用 inproc: 传输以及 pub/sub 消息传递模式吗

    设想 我们正在评估ZeroMQ 具体来说jeroMq 用于事件驱动机制 应用程序是分布式的 其中多个服务 发布者和订阅者都是服务 可以存在于同一个 jvm 中或不同的节点中 这取决于部署架构 观察 为了玩玩我创建了一个pub sub图案与i
  • 当将位图加载为 Windows 资源时,是否有办法保留 BITMAPFILEHEADER?

    我一直在使用测试一些东西SFML 1 4 http sfml dev org 简单快速的多媒体库 采用 C 和 Visual C 2008 Express Edition 为了避免我的图形程序出现外部图像 我正在测试sf Image Loa
  • 二和 Leetcode 解释、Hashmap、Javascript

    我只是想知道谁能一步一步解释这个解决方案的算法 我不知道哈希图是如何工作的 您能否还提供一个使用哈希图的基本示例 以便我理解该算法 谢谢你 var twoSum function nums target let hash for let i