当前位置: 首页 > news >正文

【Hot100算法刷题集】哈希-01-两数之和(暴力枚举再优化,也不是哈希表的对手)

在这里插入图片描述

🏠关于专栏:专栏用于记录LeetCode中Hot100专题的所有题目
🎯每日努力一点点,技术变化看得见

题目转载

题目描述

🔒link->题目跳转链接
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那 两个整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

题目示例

示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:
输入:nums = [3,3], target = 6
输出:[0,1]

题目提示

2 2 2 <= nums.length <= 1 0 4 10^4 104
− 1 0 9 -10^9 109 <= nums[i] <= 1 0 9 10^9 109
− 1 0 9 -10^9 109 <= target <= 1 0 9 10^9 109
● 只会存在一个有效答案

🔍进阶: 你可以想出一个时间复杂度小于 O ( n 2 ) O(n^2) O(n2) 的算法吗?

解题思路及代码

[1]暴力枚举

一眼可以想到的就是让所有数字两两匹配,则我们可以使用两层for循环。但题目要求不能使用同一个元素,下方代码中如果内外层循环下标相等时,即表示同一个元素,需要跳过。
在这里插入图片描述

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0; i < nums.size(); ++i){for(int j = 0; j < nums.size(); ++j){if(i == j) continue;	//表示同一个元素,跳过if(nums[i] + nums[j] == target) return {i, j};}}return {};}
};

对于两两匹配的算法来说,可以做出如下优化。上述实现代码中,当外循环为1时,它与2组合过了;但当外循环为2是,它又与1组合了1次,这出现了重复组合的情况,降低了效率。下图左侧还给出了其他重复比较的地方(2和1、3和1、3和2均出现了重复比较)。可将其优化为右侧方式,避免重复比较,提高效率。
在这里插入图片描述

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0; i < nums.size(); ++i){// 不再与小于i的元素组合for(int j = i + 1; j < nums.size(); ++j){if(nums[i] + nums[j] == target) return {i, j};}}return {};}
};

[2]哈希表

上述代码的效率是 O ( N 2 ) O(N^2) O(N2)的,效率比较低。我们可以借助于哈希表将时间效率提高为 O ( 1 ) O(1) O(1)。逻辑思路为:构建一个哈希表,其存储的元素为一个键值对,first域为具体的数值,second域为数值在nums数组的下标;当遍历到第index元素elem时,就在哈希表中查找target-elem,如果存在则返回target-elem的second域和index即可,若不存在则将当前元素的值和下标保存到哈希表中。逻辑思路图如下图所示。
在这里插入图片描述

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> m;for(int i = 0; i < nums.size(); ++i){auto des = m.find(target - nums[i]);if(des != m.end()){return {des->second, i};}else{m[nums[i]] = i;}}return {};}
};

刷题使我快乐😭
文章如有错误,请私信或在下方留言😀

相关文章:

【Hot100算法刷题集】哈希-01-两数之和(暴力枚举再优化,也不是哈希表的对手)

&#x1f3e0;关于专栏&#xff1a;专栏用于记录LeetCode中Hot100专题的所有题目 &#x1f3af;每日努力一点点&#xff0c;技术变化看得见 题目转载 题目描述 &#x1f512;link->题目跳转链接 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中…...

基于.NET6的WPF基础总结(上)

目录 一.常用属性介绍 二、 程序退出方式 三、布局样式 3.1 Panel的附加属性ZIndex 3.2 Grid(网格)布局 3.3 UniformGrid&#xff08;均分布局&#xff09; 3.4 StackPanel&#xff08;堆积面板&#xff09; 3.5 WrapPanel&#xff08;换行面板&#xff09; 3.6 Doc…...

Nuxt3入门:资源文件(第2节)

你好同学&#xff0c;我是沐爸&#xff0c;欢迎点赞、收藏、评论和关注。 Nuxt 为资源存放提供两种选择。可以使用两个目录&#xff08;public/assets&#xff09;来处理样式表、字体或图像等资源。 public/ 此目录中的文件将按原样复制到服务器根目录中。assets/ 此目录中的…...

企业微信中嵌套的h5应用调用微信扫码功能

企业微信官方文档 1.登录企业微信后台,管理员可操作,打开应用配置应用可信域名(必须配置,否则无法调用jsapi,可信域名必须有ICP备案且在管理端验证域名归属) 配置部署后的前台域名地址 配置可信域名,部署后的服务器域名(需备案认证) 当域名权限不够时需下载文件效验,将文件放…...

Excel如何把表格变成图表

Excel如何把表格变成图表 ‌将Excel表格转换为图表‌的过程相对简单且直观&#xff0c;主要步骤包括准备数据、插入图表、设置图表格式等。 以下是详细的步骤说明&#xff1a; ‌准备数据‌&#xff1a;首先&#xff0c;在Excel表格中输入或准备好要创建图表的数据。这些数据可…...

HTTP 三、http在springboot中得应用

一、springboot处理http请求的过程 1、客户端发起HTTP请求&#xff0c;经过网络传输到服务器 HTTP请求通常由浏览器、Postman、curl或其他HTTP客户端发起&#xff0c;客户端的HTTP请求通过网络&#xff08;通常是TCP/IP协议&#xff09;传输到服务器&#xff0c;这个请求首先会…...

Java秋招面经(网搜版)

1.redis的数据结构 Redis 提供了多种高效的数据结构来满足不同的应用需求。主要包括字符串&#xff08;String&#xff09;&#xff0c;这是最基础的数据类型&#xff0c;支持存储和操作各种数据&#xff1b;哈希&#xff08;Hash&#xff09;&#xff0c;类似于键值对的集合&…...

【Android】Material Design编写更好的UI

Toolbar 对于控件ActionBar我们非常熟悉&#xff0c;就是我们常见的标题栏&#xff0c;但ActionBar只能位于活动的顶部&#xff0c;因此我们更建议使用Toolbar。在新建一个项目的时候都是默认显示ActionBar&#xff0c;我们要使用Toolbar就需要先将标题栏改为不显示 先来看看…...

剪辑视频,这四大工具助你一臂之力!

在这个数字化的时代&#xff0c;视频已成为一种重要的表达手段。无论您是专业视频制作者还是只是偶尔想要编辑一些个人视频&#xff0c;一款优秀的视频剪辑软件都将是您不可或缺的好帮手。以下是几款值得推荐的视频剪辑软件。 福昕视频剪辑 直达链接&#xff1a;www.pdf365.c…...

基于单片机的热成像测温显示系统设计

本设计基于单片机的热成像测温显示系统&#xff0c;本系统包括STM32F103C6T6微控制器、MLX90640红外温度传感器、TFT-LCD显示屏、AT24C02存储模块、报警模块、按键模块和MP3语音播报模块。其可以通过热成像传感器对被检测物体的温度进行非接触式测量&#xff0c;并能够将被测信…...

CSS系列之Float浮动(二)

一、传统网页布局 网页布局的本质&#xff1a;用 CSS 来摆放盒子&#xff0c;把盒子摆放到相应位置。CSS 提供了三种传统布局方式&#xff08;这里指的只是传统布局&#xff0c;其实还有一些特殊高级的布局方式&#xff09;&#xff1a; 标准流浮动定位 1、所谓的标准流&#…...

macos下的 sed命令安装与使用 gnu-sed

sed命令是我们在linu类系统中非常重要的一个命令, 但是在macos下面默认是没有sed命令的, 不过我们可以通过brew install gnu-sed ( 或者通过 sudo port install gsed )这个软件包来获得这个命令 GNU sed 命令安装 下面2种方式,选择一种安装即可 # brew安装 brew install gn…...

RLC(电阻、电感、电容)

RLC&#xff08;电阻、电感、电容&#xff09; 目录一、两个电阻&#xff08;R1&#xff0c;R2&#xff09;&#xff0c;电容&#xff08;C1&#xff0c;C2&#xff09;的串联/并联公式&#xff1f;二、请画出这个1ms&#xff0c; 1V的Vin脉冲信号在Vout端的大致图像1.电路图2.…...

语音测试(一)ffmpeg视频转音频

视频转音频 下载ffmpeg工具进入bin目录cmd进入控制台输入命令 ffmpeg.exe -i ./视频.mp4 ./音频.wav命令说明 ffmpeg -i input.mp4 output.mkv FFmpeg 可能会尝试自动选择合适的编码器对视频和音频进行重新编码&#xff0c;以便适应 MKV 格式的要求ffmpeg -i input.mp4 -c c…...

计算机网络八股文之TCP协议

TCP/IP模型 链路层 物理层&#xff1a;主要定义物理设备标准&#xff0c;如网线的接口类型、光纤的接口类型、各种传输介质的传输速率等。它的主要作用是传输比特流&#xff08;就是由1、0转化为电流强弱来进行传输&#xff0c;到达目的地后再转化为1、0&#xff0c;也就是我们…...

【linux】linux中如何通过stress进行压力测试,原理解析与应用实战

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全…...

python用波形显示udp数据实现一个模拟示波器

显示端代码: import socket import matplotlib.pyplot as plt import matplotlib.animation as animation import numpy as np# UDP setup udp_ip = 0.0.0.0 # Listen on all network interfaces udp_port = 12345 sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)…...

开源通用验证码识别OCR —— DdddOcr 源码赏析(二)

文章目录 前言DdddOcr分类识别调用识别功能classification 函数源码classification 函数源码解读1. 分类功能不支持目标检测2. 转换为Image对象3. 根据模型配置调整图片尺寸和色彩模式4. 图像数据转换为浮点数据并归一化5. 图像数据预处理6. 运行模型&#xff0c;返回预测结果 …...

【个人笔记】VCS工具与命令

Title&#xff1a;VCS工具学习 一 介绍 是什么&#xff1f; VCS (Verilog Compiler Simulator) 是synopsys的verilog 仿真软件&#xff0c;竞品有Mentor公司的Modelsim、Cadence公司的NC-Verilog、Verilog—XL. VCS能够 分析、编译 HDL的design code&#xff0c;同时内置了 仿…...

面试进去8分钟就出来了,问的问题有点变态。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%,这…...

从电解到瓷片:不同材质去耦电容在电路设计中的最佳应用场景对比

从电解到瓷片&#xff1a;不同材质去耦电容在电路设计中的最佳应用场景对比 当你在设计一块电路板时&#xff0c;是否曾经为电源引脚旁那个小小的电容而犹豫不决&#xff1f;是选择便宜的电解电容&#xff0c;还是性能稳定的瓷片电容&#xff0c;亦或是价格不菲的钽电容&#x…...

GLM-OCR硬件优化指南:为GPU部署调整显存与算力配置

GLM-OCR硬件优化指南&#xff1a;为GPU部署调整显存与算力配置 如果你正在尝试部署GLM-OCR模型&#xff0c;是不是也遇到过这样的困惑&#xff1a;明明选了看起来不错的GPU&#xff0c;但推理时要么爆显存&#xff0c;要么速度慢得让人着急&#xff0c;钱花了效果却没达到预期…...

网络信息安全技术术语对照表

类别术语中文术语英文术语说明基础技术类加密encryption将明文数据通过特定算法和密钥转换为密文数据的过程&#xff0c;目的是确保数据在存储、传输过程中不被未授权方获取和理解。基础技术类解密decryption将加密后的密文数据&#xff0c;通过对应的算法和密钥还原为原始明文…...

FlinkX异构数据同步:从安装到实战的5个关键技巧

FlinkX异构数据同步&#xff1a;从安装到实战的5个关键技巧 在数据驱动的时代&#xff0c;企业常常面临不同数据源之间高效同步的挑战。FlinkX作为一款基于Apache Flink的分布式数据同步工具&#xff0c;凭借其强大的异构数据源支持能力和灵活的插件架构&#xff0c;正在成为技…...

为什么Logisim-Evolution是数字电路学习的最佳选择?

为什么Logisim-Evolution是数字电路学习的最佳选择&#xff1f; 【免费下载链接】logisim-evolution Digital logic design tool and simulator 项目地址: https://gitcode.com/gh_mirrors/lo/logisim-evolution 在数字逻辑的世界里&#xff0c;你是否曾为理解抽象的逻辑…...

NFT系统开发:在数字荒原上播种「文明契约」

——解码下一代价值互联网的基础设施革命引言&#xff1a;当数字资产成为新大陆的「土地证」2025年&#xff0c;全球NFT市场规模突破870亿美元&#xff0c;从艺术收藏到房地产契约&#xff0c;从游戏道具到知识产权&#xff0c;NFT正在重构人类对"所有权"的认知。在物…...

React on Rails 国际化(i18n)终极指南:如何快速实现多语言支持

React on Rails 国际化(i18n)终极指南&#xff1a;如何快速实现多语言支持 【免费下载链接】react_on_rails Integration of React Webpack Rails including server-side rendering of React, enabling a better developer experience and faster client performance. 项目…...

2025年中国市场SCA工具深度评测:国产化浪潮下的安全新选择

随着数字化转型进入深水区&#xff0c;软件供应链安全已成为企业不可忽视的战略要地。2025年&#xff0c;在信创政策持续深化与国产化替代加速的双重背景下&#xff0c;软件成分分析(SCA)工具作为DevSecOps体系中的关键一环&#xff0c;正迎来前所未有的市场机遇与挑战。这场由…...

MSI-X 虚拟化

MSI-X 虚拟化是 PCIe 设备在虚拟化环境中&#xff0c;将硬件 MSI-X 中断能力通过软件模拟、IOMMU 重映射或 SR-IOV 硬件隔离等技术&#xff0c;安全、高效地分配给多个虚拟机&#xff08;Guest&#xff09;的核心机制。它解决了传统 INTx 中断共享、MSI 向量不足的问题&#xf…...

技术对业务的赋能

技术对业务的赋能 技术不只是实现需求&#xff0c;更是提升效率、降低成本、放大增长、控制风险&#xff0c;最终帮业务赚到更多、跑得更快、活得更稳。 1. 提升效率&#xff0c;降本增效 自动化流程&#xff1a;表单、审批、报表自动生成&#xff0c;减少人工重复劳动组件化/低…...