【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-两数之和(暴力枚举再优化,也不是哈希表的对手)
🏠关于专栏:专栏用于记录LeetCode中Hot100专题的所有题目 🎯每日努力一点点,技术变化看得见 题目转载 题目描述 🔒link->题目跳转链接 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中…...
基于.NET6的WPF基础总结(上)
目录 一.常用属性介绍 二、 程序退出方式 三、布局样式 3.1 Panel的附加属性ZIndex 3.2 Grid(网格)布局 3.3 UniformGrid(均分布局) 3.4 StackPanel(堆积面板) 3.5 WrapPanel(换行面板) 3.6 Doc…...
Nuxt3入门:资源文件(第2节)
你好同学,我是沐爸,欢迎点赞、收藏、评论和关注。 Nuxt 为资源存放提供两种选择。可以使用两个目录(public/assets)来处理样式表、字体或图像等资源。 public/ 此目录中的文件将按原样复制到服务器根目录中。assets/ 此目录中的…...
企业微信中嵌套的h5应用调用微信扫码功能
企业微信官方文档 1.登录企业微信后台,管理员可操作,打开应用配置应用可信域名(必须配置,否则无法调用jsapi,可信域名必须有ICP备案且在管理端验证域名归属) 配置部署后的前台域名地址 配置可信域名,部署后的服务器域名(需备案认证) 当域名权限不够时需下载文件效验,将文件放…...
Excel如何把表格变成图表
Excel如何把表格变成图表 将Excel表格转换为图表的过程相对简单且直观,主要步骤包括准备数据、插入图表、设置图表格式等。 以下是详细的步骤说明: 准备数据:首先,在Excel表格中输入或准备好要创建图表的数据。这些数据可…...
HTTP 三、http在springboot中得应用
一、springboot处理http请求的过程 1、客户端发起HTTP请求,经过网络传输到服务器 HTTP请求通常由浏览器、Postman、curl或其他HTTP客户端发起,客户端的HTTP请求通过网络(通常是TCP/IP协议)传输到服务器,这个请求首先会…...
Java秋招面经(网搜版)
1.redis的数据结构 Redis 提供了多种高效的数据结构来满足不同的应用需求。主要包括字符串(String),这是最基础的数据类型,支持存储和操作各种数据;哈希(Hash),类似于键值对的集合&…...
【Android】Material Design编写更好的UI
Toolbar 对于控件ActionBar我们非常熟悉,就是我们常见的标题栏,但ActionBar只能位于活动的顶部,因此我们更建议使用Toolbar。在新建一个项目的时候都是默认显示ActionBar,我们要使用Toolbar就需要先将标题栏改为不显示 先来看看…...
剪辑视频,这四大工具助你一臂之力!
在这个数字化的时代,视频已成为一种重要的表达手段。无论您是专业视频制作者还是只是偶尔想要编辑一些个人视频,一款优秀的视频剪辑软件都将是您不可或缺的好帮手。以下是几款值得推荐的视频剪辑软件。 福昕视频剪辑 直达链接:www.pdf365.c…...
基于单片机的热成像测温显示系统设计
本设计基于单片机的热成像测温显示系统,本系统包括STM32F103C6T6微控制器、MLX90640红外温度传感器、TFT-LCD显示屏、AT24C02存储模块、报警模块、按键模块和MP3语音播报模块。其可以通过热成像传感器对被检测物体的温度进行非接触式测量,并能够将被测信…...
CSS系列之Float浮动(二)
一、传统网页布局 网页布局的本质:用 CSS 来摆放盒子,把盒子摆放到相应位置。CSS 提供了三种传统布局方式(这里指的只是传统布局,其实还有一些特殊高级的布局方式): 标准流浮动定位 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(电阻、电感、电容) 目录一、两个电阻(R1,R2),电容(C1,C2)的串联/并联公式?二、请画出这个1ms, 1V的Vin脉冲信号在Vout端的大致图像1.电路图2.…...
语音测试(一)ffmpeg视频转音频
视频转音频 下载ffmpeg工具进入bin目录cmd进入控制台输入命令 ffmpeg.exe -i ./视频.mp4 ./音频.wav命令说明 ffmpeg -i input.mp4 output.mkv FFmpeg 可能会尝试自动选择合适的编码器对视频和音频进行重新编码,以便适应 MKV 格式的要求ffmpeg -i input.mp4 -c c…...
计算机网络八股文之TCP协议
TCP/IP模型 链路层 物理层:主要定义物理设备标准,如网线的接口类型、光纤的接口类型、各种传输介质的传输速率等。它的主要作用是传输比特流(就是由1、0转化为电流强弱来进行传输,到达目的地后再转化为1、0,也就是我们…...
【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. 运行模型,返回预测结果 …...
【个人笔记】VCS工具与命令
Title:VCS工具学习 一 介绍 是什么? VCS (Verilog Compiler Simulator) 是synopsys的verilog 仿真软件,竞品有Mentor公司的Modelsim、Cadence公司的NC-Verilog、Verilog—XL. VCS能够 分析、编译 HDL的design code,同时内置了 仿…...
面试进去8分钟就出来了,问的问题有点变态。。。
从小厂出来,没想到在另一家公司又寄了。 到这家公司开始上班,加班是每天必不可少的,看在钱给的比较多的份上,就不太计较了。没想到一纸通知,所有人不准加班,加班费不仅没有了,薪资还要降40%,这…...
实时手机检测模型在安防监控中的应用:自动识别违规使用手机行为
实时手机检测模型在安防监控中的应用:自动识别违规使用手机行为 1. 应用场景与需求分析 1.1 安防监控中的手机检测痛点 在考场、保密场所、生产车间等特殊环境中,违规使用手机可能带来严重的安全隐患。传统人工监控方式存在以下问题: 人力…...
带行星传动装置的电动螺旋拆卸器设计【说明书 cad图纸 solidworks三维】
在机械维修与设备拆解领域,传统工具常因扭矩不足或操作空间受限,导致螺栓卡滞、部件损坏等问题。带行星传动装置的电动螺旋拆卸器通过集成行星齿轮系统与电动驱动模块,有效解决了这一痛点。其核心作用在于利用行星齿轮的行星轮系结构…...
Anything V5进阶使用:结合REST API实现批量自动生成二次元图像
Anything V5进阶使用:结合REST API实现批量自动生成二次元图像 1. 项目概述 Anything V5是基于Stable Diffusion技术的高质量二次元图像生成模型,相比基础版本,它在动漫风格图像生成方面表现出色。本教程将重点介绍如何通过REST API实现批量…...
脚本开发必看:随机数使用中的3个常见误区及正确写法(按键精灵版)
脚本开发必看:随机数使用中的3个常见误区及正确写法(按键精灵版) 在自动化脚本开发中,随机数功能就像一把双刃剑——用得好能让脚本行为更接近人类操作,用得不好则可能导致不可预测的bug。特别是在按键精灵这类工具中&…...
公众号流量分成大涨!后公众号时代如何运营?流量商店旗下的互粉平台成增粉利器!
“上个月流量主收入终于突破5000元了!”深夜,运营“职场进化论”公众号的小林在朋友圈晒出后台截图。一年前,这个只有几百粉丝的账号月收入还不到100元。而如今,像小林这样依靠公众号流量分成实现可观收入的创作者正越来越多。 20…...
AHT20传感器数据不准?可能是你的CRC校验没做对!一个真实案例的排查与修复
AHT20传感器数据异常?CRC校验可能是你忽略的关键环节 当你在嵌入式项目中集成AHT20温湿度传感器时,是否遇到过数据偶尔跳变或明显失真的情况?这个问题困扰过不少开发者,而解决方案往往藏在一个容易被忽视的细节里——CRC校验。让我…...
C++和OpenGL实现3D游戏编程【连载16】——详解三维坐标转二维屏幕坐标(向量和矩阵操作实战)(附源码)
🔥C++和OpenGL实现3D游戏编程【目录】 1、本节课要实现的内容 在上一课我们了解了着色器,了解了部分核心模式编程内容,从中接触到了线性代数中向量和矩阵相关知识,我们已经能够感受到向量和矩阵在OpenGL编程中的重要性。特别是后期用去了解融合、光照效果,构建自己的三维…...
Haskell编译器优化:wiwinwlh GHC内部机制详解
Haskell编译器优化:wiwinwlh GHC内部机制详解 【免费下载链接】wiwinwlh What I Wish I Knew When Learning Haskell 项目地址: https://gitcode.com/gh_mirrors/wi/wiwinwlh wiwinwlh项目(What I Wish I Knew When Learning Haskell)…...
OpenClaw多模态实践:千问3.5-27B图片理解+文件整理自动化
OpenClaw多模态实践:千问3.5-27B图片理解文件整理自动化 1. 为什么需要自动化图片管理 上周整理项目资料时,我发现桌面上散落着237张截图——有会议纪要片段、代码报错提示、参考文档关键页,甚至还有随手截的灵感草图。手动分类这些文件花了…...
WebLaTeX终极指南:免费在线LaTeX编辑器,让学术写作变得如此简单
WebLaTeX终极指南:免费在线LaTeX编辑器,让学术写作变得如此简单 【免费下载链接】WebLaTex A complete alternative for Overleaf with VSCode Web Git Integration Copilot Grammar & Spell Checker Live Collaboration Support. Based on Git…...
