草庐IT

Leetcode题1两数之和 JavaScript语言

徐风吟 2023-03-28 原文

1. 两数之和

方案一，暴力双循环

读完题目，马上能想到的方案就是双循环，挨个排查，写出来也很快：

var twoSum = function(nums, target) {
    const len = nums.length;
    for (let i = 0; i < len; i+=1) {
        const left = nums[i];
        for (let j = i+1; j < len; j+=1) {
            const right = nums[j]
            if (left + right === target) {
                return [i, j]
            }
        }
    }
};

上面方案，最大的问题就是时间复杂度为 O(n^2)，所以我们可以想办法在此基础上优化。

方案二，空间换时间（Map）

方案一的思路是，从头到尾挨个去计算数组中任意两个元素的和，然后与给定结果值进行比较，从而找到目标索引，这就导致必须得进行 O(n^2) 复杂度的双循环，效率低下。为了干掉双循环，我们不得不转换思考方式，如何才能在一次迭代中就实现题目要求呢。

题目本质是找到符合要求的两个数组元素的索引，不是非要双循环迭代以此两两配对求和后再比较。既然已经知道目标值，可以采取空间换时间的策略，用一个结构存储遍历过的每个元素和索引，然后我们完全可以仅仅只在一次迭代中，就实现题目要求。具体思路如下：

  1. 对于当前遍历元素，计算其相对于目标值所需的另一个加数
  2. 查找存储器是否有这样的加数，如果有，取得此加数的索引，算法结束
  3. 如果存储结构中找不到这样的加数，则将当前元素及其索引存入存储器，供后续遍历到的元素使用

比如，[2, 7, 11, 15]目标9，对于 2，其需要加数7，但是现在存储器为空，所以我们将元素2和其索引0存入存储器。然后当遍历来到元素7时，其需要加数2，查找存储结构发现有2，取得2的索引后与7的索引一同返回，问题即得解。

这里可以发现，对于当前遍历的元素，我们需要存储两个东西：一个东西是数组元素，一个是元素索引；且这两个东西是有关系的，应该两个一组一起存储。另外，我们的存储器必须具有 O(1) 读/写速度，基于以上考虑，我们选择使用 Map这种类型来做存储器。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const len = nums.length
    const map = new Map()

    for (let i = 0; i < len; i+=1) {
        const currElem = nums[i]
        const needNum = target - currElem

        if (map.has(needNum)) {
            return [map.get(needNum), i]
        }

        map.set(currElem, i)
    }

    return []
};

之和JavaScriptcode双循环const算法与数据结构

有关Leetcode题1两数之和 JavaScript语言的更多相关文章

  1. ruby - 如何将脚本文件的末尾读取为数据文件(Perl 或任何其他语言) - 2

    我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚

  2. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  3. Unity 热更新技术 | （三） Lua语言基本介绍及下载安装 - 2

    ?博客主页：https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创，首发于CSDN??学习专栏推荐：Unity系统学习专栏?游戏制作专栏推荐：游戏制作?Unity实战100例专栏推荐：Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正！?未来很长，值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------

  4. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

  5. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  6. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2

    我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

  7. ruby - 如何保持我不常用的编程语言技能 - 2

    关闭。这个问题是off-topic.它目前不接受答案。想改进这个问题吗？Updatethequestion所以它是on-topic用于堆栈溢出。关闭11年前。Improvethisquestion我不经常使用ruby​​-通常它加起来相当于每两个月或更长时间编写一次脚本。我的大部分编程都是使用C++进行的，这与ruby​​有很大不同。由于我与ruby​​之间的差距如此之大，我总是忘记语言的基本方面(比如解析文本文件和其他简单的东西)。我想每天练习一些基本的东西，我想知道是否有一些我可以订阅的网站，并且会向我发送当天的Ruby问题或类似的东西。有人知道这样的站点/Internet服务吗？

  8. ruby-on-rails - 如果特定语言环境中缺少翻译，如何配置 i18n 以使用 en 语言环境？ - 2

    如果特定语言环境中缺少翻译，如何配置i18n以使用en语言环境翻译？当前已插入翻译缺失消息。我正在使用RoR3.1。 最佳答案 找到相似的question这里是答案:#application.rb#railswillfallbacktoconfig.i18n.default_localetranslationconfig.i18n.fallbacks=true#railswillfallbacktoen,nomatterwhatissetasconfig.i18n.default_localeconfig.i18n.fallback

  9. ruby - 在 Mechanize 中使用 JavaScript 单击链接 - 2

    我有这个:AccountSummary我想单击该链接，但在使用link_to时出现错误。我试过:bot.click(page.link_with(:href=>/menu_home/))bot.click(page.link_with(:class=>'top_level_active'))bot.click(page.link_with(:href=>/AccountSummary/))我得到的错误是:NoMethodError:nil:NilClass的未定义方法“[]” 最佳答案 那是一个javascript链接。Mechan

  10. ruby-on-rails - 如何通过 URL 更改语言环境？ - 2

    在我的双语Rails4应用程序中，我有一个像这样的LocalesController:classLocalesController用户可以通过此表单更改其语言环境:deflocale_switcherform_tagurl_for(:controller=>'locales',:action=>'change_locale'),:method=>'get',:id=>'locale_switcher'doselect_tag'set_locale',options_for_select(LANGUAGES,I18n.locale.to_s)end这有效。但是，目前用户无法通过URL更改

随机推荐