[算法刷题积累] 两数之和以及进阶引用

 

两数之和很经典,通常对于首先想到的就是暴力的求解,当然这没有问题,但是我们如果想要追求更优秀算法,就需要去实现更加简便的复杂度。

        这里就要提到我们的哈希表法: 我们可以使用unordered_map去实现,也可以根据题目,用数组去模拟哈希表,两种方式选择合适的就好。

        哈希表通过记录来某一键值是否存在,如果存在则可进一步访问pair中的second类型变量,通过这一系列的组合,就可以用哈希表简化大部分问题。

        如本道题,二数之和,就是找寻数组中两个和为target的数,并且返回其下标。

        那么数据的值就key,对应的下标就是value。而且题目有要求:你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现,所以我们要先去寻找hash表中键值 target-nums[i]是否存在,存在就说明再nums[i]之前,就有与nums[i]和为target的值出现,所以返回 键值对应的Value(下标)和当前的i即可。   如果没有,则将当前的key(数据的值)添加并且记录其对应的下标。

、变式应用:

  •  此道题目,同样很容易想到暴力的解法,但是对于数据庞大的此道题会出现超时的结果。所以我们就要去优化算法结构,正好此题目与两个数据之间的关系有关的,所以很容易想到两数之和的哈希表解法。
  • 题目不再是返回满足条件的下标组合,而是输出满足条件下标的对数。所以这里的key键值和value的意义也要对应修改:key指代出现的数据对24取模后的值,value代表数据对24取模之后出现key的次数。
  • 举例比如:23出现,对24取模操作,得到23,那么hash[23]++(hash[23]的值代表出现次数)。
  • 所以对于两个数有必须要有关系:     ( X + Y )%24 == 0

所以就有下面的关系:

        

最后得到关系:   x%24 = (24-y%24)%24

利用这个关系式子,可以找到能与当前数据匹配之后能被24整除的数据对的个数。

具体操作:

1.寻找与当前数据满足条件的数据是否存在,如果存在,则统计次数。

2.如果没有,则将当前数据与24的取模作为key键值取更新value的值。(第一步和第二步一定不能反,如果倒过来,就不满足题目  i < j 

遍历一次整个数组,就可以统计出所有的对数即可。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/722530.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】线程(二:线程控制)

本篇文章主要围绕线程控制来进行展开。 主题思路是以create与join两个接口展开。 目录 pthread_create 与 pthread_join:pthread_create:pthread_join: 代码&#xff1a;问题一&#xff1a;主线程与新线程谁先退出&#xff1f;问题二&#xff1a;哪个线程应该最后退出&#xf…

【关键点检测和描述】SuperPoint

一、引言 论文&#xff1a; SuperPoint: Self-Supervised Interest Point Detection and Description 作者&#xff1a; Magic Leap 代码&#xff1a; SuperPoint 特点&#xff1a; 提出Homographic Adaptation策略&#xff0c;提升模型从虚拟数据迁移到真实数据的表现&#x…

邻氯苯甲酰氯在医药、农药等领域应用广泛 市场需求稳定且有增长趋势

邻氯苯甲酰氯在医药、农药等领域应用广泛 市场需求稳定且有增长趋势 邻氯苯甲酰氯又称为2-氯苯甲酰氯、氯化邻氯苯甲酰&#xff0c;化学式为C7H4Cl2O&#xff0c;是一种化学物质&#xff0c;外观为黄色液体&#xff0c;不溶于水&#xff0c;溶于醇、醚、丙酮&#xff0c;有强烈…

第100+12步 ChatGPT学习:R实现KNN分类

基于R 4.2.2版本演示 一、写在前面 有不少大佬问做机器学习分类能不能用R语言&#xff0c;不想学Python咯。 答曰&#xff1a;可&#xff01;用GPT或者Kimi转一下就得了呗。 加上最近也没啥内容写了&#xff0c;就帮各位搬运一下吧。 二、R代码实现KNN分类 &#xff08;1&a…

API 设计技巧:基础知识与实践的方法

在这篇深入探讨中&#xff0c;我们将从基础开始&#xff0c;逐步介绍 API 设计&#xff0c;并探讨定义卓越API的最佳实践。 作为一名开发者&#xff0c;你可能已经熟悉了许多这些概念&#xff0c;但我将提供详细解释&#xff0c;以加深你的理解。 API 设计&#xff1a;电子商…

图纸管理最佳实践:从混乱到有序的转变

图纸管理最佳实践&#xff1a;从混乱到有序的转变 在工程项目中&#xff0c;图纸是不可或缺的重要资料&#xff0c;它们承载着设计者的智慧与心血。然而&#xff0c;随着项目的推进和时间的推移&#xff0c;图纸管理往往变得混乱不堪&#xff0c;给项目的顺利进行带来诸多不便。…

ROS(四)

write in advance 实验四&#xff0c;在经历了实验三的失败后&#xff0c;卷土重来。 幸运的是&#xff0c;此次实验很简单&#xff0c;很快就能搞定。 Part one 使用指令查看自己摄像头的设备号&#xff0c;如果报错&#xff0c;且你为虚拟机&#xff0c;可能是未在虚拟机处…

Java学习 (二)关键字、标识符、数组

一、关键字 我们第一章案例中有很多关键字&#xff0c;比如class、public、static、void等&#xff0c;这些关键字依旧被java定义好了&#xff0c;可以拿来用&#xff0c;不需要死记硬背&#xff0c;按照官方文档查询即可 #官方文档 https://docs.oracle.com/javase/tutorial/j…

docker-compose设置永久启动、自动重启

步骤一 找到 docker-compose.yml 文件 步骤二 vim 打开文件 找到 image: PS&#xff1a;就是为了对齐格式 步骤三 在其下方添加&#xff1a; restart: always而后保存即可

打开nginx连接的php页面报错502

目录 问题描述&#xff1a; 原因&#xff1a; 1. 使用 Unix 域套接字&#xff08;Unix Socket&#xff09; 区别和优势&#xff1a; 2. 使用 TCP/IP 套接字 区别和优势&#xff1a; 如何选择 扩展&#xff1a;Rocky_Linux9.4安装PHP的步骤&#xff1a; 使用Remi存储库…

Wifi通信协议:WEP,WPA,WPA2,WPA3,WPS

前言 无线安全性是保护互联网安全的重要因素。连接到安全性低的无线网络可能会带来安全风险&#xff0c;包括数据泄露、账号被盗以及恶意软件的安装。因此&#xff0c;利用合适的Wi-Fi安全措施是非常重要的&#xff0c;了解WEP、WPA、WPA2和WPA3等各种无线加密标准的区别也是至…

通过防抖动代码解决ResizeObserver loop completed with undelivered notifications.

通过防抖动代码解决ResizeObserver loop completed with undelivered notifications. 一、报错内容二、解决方案解释&#xff1a; 一、报错内容 我通过el-tabs下的el-tab-pane切换到el-table出现的报错&#xff0c;大致是渲染宽度出现了问题 二、解决方案 扩展原生的 Resiz…

Android 应用加固与重签名—使用AndroidStudio自带工具 apksigner

由 AndroidStudio 生成的release版本的app有自己的签名&#xff0c;但当应用加固后会删除原签名&#xff0c;需要重新签名。 一、加固方式&#xff1a; 使用基础版的腾讯云&#xff08;乐固&#xff09;进行免费加固&#xff0c;上传软件后等待在线加固完成后下载 apk 即可。…

vue3+ts+vite集成eslint

项目中安装eslint yarn add eslint -Deslint初始化 npx eslint --init按照下方操作即可 安装typescript-eslint/parser yarn add typescript-eslint/parser -D安装vite-plugin-eslint2 yarn add vite-plugin-eslint2 -D配置vite-plugin-eslint2 // vite.config.ts import …

钡铼技术BL104在环境监测站多协议采集保障数据全面准确

随着工业化和城市化进程的加快&#xff0c;环境污染问题日益严重&#xff0c;环境监测站在保护生态环境、保障公众健康中的作用变得越来越重要。钡铼技术PLC物联网关BL104&#xff0c;为环境监测站提供了一种高效、可靠的多协议数据采集解决方案&#xff0c;保障了监测数据的全…

如何实现对文件发送全生命周期的外发管理?

在日常工作中&#xff0c;我们需要经常和企业外部的机构或者个人&#xff0c;发送一些企业内部的文档或者图纸等资料。但企业在文件外发管理上&#xff0c;仍存在一定漏洞&#xff0c;有些员工会通过一些手段&#xff0c;将重要核心文件数据发过去&#xff0c;包括但不仅限于以…

【数据结构(邓俊辉)学习笔记】二叉搜索树02——查找、插入和删除

文章目录 1.概述2. 查找2.1 查找&#xff1a;算法2.2 查找&#xff1a;理解2.3 查找&#xff1a;实现2.4 查找&#xff1a;语义 3. 插入3.1 插入&#xff1a;算法3.2 插入&#xff1a;实现 4. 删除4.1 删除&#xff1a;框架4.2 删除&#xff1a;单分支4.3 删除&#xff1a;双分…

MySQL----redo log重做日志原理及流程

重做日志 redo log&#xff1a;重做日志&#xff0c;用于记录事务操作的变化&#xff0c;确保事务的持久性。redo log是在事务开始后就开始记录&#xff0c;不管事务是否提交都会记录下来&#xff0c;在异常发生时&#xff08;如数据持久化过程中掉电&#xff09;&#xff0c;…

笔记-python里面的xlrd模块详解

那我就一下面积个问题对xlrd模块进行学习一下&#xff1a; 1.什么是xlrd模块&#xff1f; 2.为什么使用xlrd模块&#xff1f; 3.怎样使用xlrd模块&#xff1f; 1.什么是xlrd模块&#xff1f; ♦python操作excel主要用到xlrd和xlwt这两个库&#xff0c;即xlrd是读excel&…

成都百洲文化传媒有限公司助力商家扬帆远航

在数字经济的浪潮中&#xff0c;电商行业如日中天&#xff0c;成都百洲文化传媒有限公司正是这一领域的佼佼者。作为一家专注于电商服务的传媒公司&#xff0c;百洲文化以其专业的服务、创新的理念和卓越的成果&#xff0c;在业内树立了良好的口碑&#xff0c;成为众多商家信赖…