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

力扣第一题 哈希解法 O(n)时间复杂度

题目:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那俩个整数,并返回它们的数组下标。

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

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

题解代码:

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {// 创建一个哈希表,用于存储数组中的元素及其对应的索引unordered_map<int, int> sum_map;// 遍历数组中的每一个元素for(int i = 0; i < nums.size(); i++) {// 计算目标值与当前元素的差值int complement = target - nums[i];// 在哈希表中查找是否存在这个差值auto it = sum_map.find(complement);// 如果找到了差值,说明之前已经遍历过这个差值对应的元素if(it != sum_map.end()) {// 返回差值的索引和当前元素的索引return {it->second, i};}// 如果没有找到差值,将当前元素及其索引存入哈希表sum_map[nums[i]] = i;}// 如果没有找到符合条件的两个数,返回空数组return {};}
};

题解分析:

假设 nums = [2, 7, 11, 15]target = 9

  • 第一次迭代:i = 0nums[i] = 2complement = 9 - 2 = 7。哈希表中没有 7,将 2 存入哈希表。

  • 第二次迭代:i = 1nums[i] = 7complement = 9 - 7 = 2。哈希表中有 2,返回 2 的索引 0 和当前索引 1,即 [0, 1]

时间复杂度

  • 时间复杂度:O(n),其中 n 是数组 nums 的长度。我们只需要遍历一次数组,每次查找哈希表的时间复杂度是 O(1)。

  • 空间复杂度:O(n),哈希表最多存储 n 个元素。

这个算法通过使用哈希表来存储已经遍历过的元素及其索引,从而在 O(1) 的时间内查找是否存在符合条件的差值,大大提高了效率。

 

相关文章:

力扣第一题 哈希解法 O(n)时间复杂度

题目&#xff1a; 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那俩个整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案&#xff0c;并且你不能使用两次相同的元素。 你可以按任意顺序返…...

elementui: el-dialog的header设置样式不生效

问&#xff1a; el-dialog的header设置样式不生效 回答&#xff1a; 场景&#xff1a; <el-dialogv-model"dialogVisible"width"800px":before-close"beforeClose"append-to-body:close-on-click-modal"false"title"增加文…...

libpcap 的使用

1.libpcap的模式 有线环境: 使用混杂模式promisous&#xff0c;完成监听无线环境: 使用监听模式monitor&#xff0c;完成监听 2.交叉编译libpcap 设置好交叉编译工具链后下载libpcap源码使用configure进行构建&#xff1a;–disable-shared 构建静态库&#xff0c;–host 、…...

ArcGISPro AA表O_Name字段 内容 复制到BB表BB字段里

import arcpy# 设置工作空间和要处理的表路径 resource_shape_table r"AA表.shp" # 源表路径 resource_assets_table r"BB表.shp" # 目标表路径# 使用 SearchCursor 读取源表中的 O_Name 字段 with arcpy.da.SearchCursor(resource_shape_table, [O_Na…...

2.5 使用注解进行单元测试详解

Mockito 使用注解进行单元测试详解 Mockito 提供了一系列注解来简化测试代码的编写&#xff0c;减少手动创建和管理 Mock 对象的样板代码。结合 JUnit 5&#xff0c;可以更高效地构建清晰、易维护的单元测试。 1. 核心注解概览 注解作用Mock创建并注入一个 Mock 对象&#xf…...

当没有OpenGL时,Skia如何绘制?

Skia 是可以在没有 OpenGL 的情况下进行图形绘制的&#xff0c;但是具体能否成功绘制图形&#xff0c;取决于 Skia 是如何配置的&#xff0c;以及平台上是否提供了其他的底层图形 API。 Skia 的底层依赖 Skia 的目标是提供一种跨平台的 2D 图形绘制接口。为了加速图形渲染&…...

SaaS+AI应用架构:业务场景、智能体、大模型、知识库、传统工具系统

SaaSAI应用架构&#xff1a;业务场景、智能体、大模型、知识库、传统工具系统 大家好&#xff0c;我是汤师爷~ 在SaaS与AI应用的演进过程中&#xff0c;合理的架构设计至关重要。本节将详细介绍其五个核心层次&#xff1a; 业务场景层&#xff1a;发现和确定业务场景智能体层…...

Go 语言中如何高效地处理集合

文章精选推荐 1 JetBrains Ai assistant 编程工具让你的工作效率翻倍 2 Extra Icons&#xff1a;JetBrains IDE的图标增强神器 3 IDEA插件推荐-SequenceDiagram&#xff0c;自动生成时序图 4 BashSupport Pro 这个ides插件主要是用来干嘛的 &#xff1f; 5 IDEA必装的插件&…...

布隆过滤器到底是什么东西?它有什么用

布隆过滤器&#xff1a;用概率换空间的奇妙数据结构 引言&#xff1a;当空间成为奢侈品 在互联网每天产生2.5万亿字节数据的时代&#xff0c;Google每秒处理超过9万次搜索请求&#xff0c;Redis缓存系统支撑着百万级QPS的访问。面对如此海量的数据处理需求&#xff0c;传统的…...

【数据结构初阶第十节】队列(详解+附源码)

好久不见。。。别不开心了&#xff0c;听听喜欢的歌吧 必须有为成功付出代价的决心&#xff0c;然后想办法付出这个代价。云边有个稻草人-CSDN博客 目录 一、概念和结构 二、队列的实现 Queue.h Queue.c test.c Relaxing Time&#xff01; ————————————《有没…...

沪深300股指期权能对股指期货进行完全套保吗?

锦鲤三三每日分享期权知识&#xff0c;帮助期权新手及时有效地掌握即市趋势与新资讯&#xff01; 沪深300股指期权能对股指期货进行完全套保吗&#xff1f; 沪深300股指期权是以沪深300指数为标的物的期权&#xff0c;而沪深300股指期货则是以该指数作为标的的期货合约。 理…...

JAVA学习第三天

继承关系变量访问的特点 01.方法中找 02.子类变量定义中找 03.父类中找 this和super关键字的使用区别&#xff1a; super父类构造函数的使用&#xff1a; 使用子类构造函数时&#xff0c;都会初始化父类的数据&#xff0c;自动调用父类的无参构造函数 super内存图——007 继…...

win11电脑其他WiFi可以连,只有一个WiFi连不上

这个问题卡了一小会&#xff0c;查了一些资料 后面发现 点击“诊断网络问题” 显示没有响应 第一步 重启wlan网络适配器 解决&#xff01;&#xff01;&#xff01; 重新连接那个有问题的wifi&#xff0c;丝滑连接&#xff01;...

leetcode_1760 袋子里最少数目的球

1. 题意 给定一个数组&#xff0c;和一个最多次操作次数。每次操作可以将数组中的一个数 x x x分成两个数 t x − t t\quad x-t tx−t。问 m a x O p e r a t i o n C n t maxOperationCnt maxOperationCnt次操作后&#xff0c;数组中最大的数最小的值是多少。 2. 题解 这个…...

Python 面向对象的三大特征

前言&#xff1a;本篇讲解面向对象的三大特征&#xff08;封装&#xff0c;继承&#xff0c;多态&#xff09;&#xff0c;还有比较细致的&#xff08;类属性类方法&#xff0c;静态方法&#xff09;&#xff0c;分步骤讲解&#xff0c;比较适合理清楚三大特征的思路 面向对象的…...

Linux下的进程切换与调度

目录 1.进程的优先级 优先级是什么 Linux下优先级的具体做法 优先级的调整为什么要受限 2.Linux下的进程切换 3.Linux下进程的调度 1.进程的优先级 我们在使用计算机的时候&#xff0c;通常会启动多个程序&#xff0c;这些程序最后都会变成进程&#xff0c;但是我们的硬…...

面向对象程序设计-实验六

7-1 函数重载&#xff08;数据类型不同&#xff09; 代码清单&#xff1a; #include<iostream> using namespace std; class axxx { public: void px(int n,int a[]) { for(int i0;i<n;i) { for(int j0;j<n-i-1;j) { int t; if(a[j]>a[j1]) { ta[j]; a[j…...

MongoDB 7 分片副本集升级方案详解(上)

#作者&#xff1a;任少近 文章目录 前言&#xff1a;Mongodb版本升级升级步骤环境1.1环境准备1.2standalone升级1.3分片、副本集升级 前言&#xff1a;Mongodb版本升级 在开始升级之前&#xff0c;请参阅 MongoDB下个版本中的兼容性变更文档&#xff0c;以确保您的应用程序和…...

【工业安全】-CVE-2022-35555- Tenda W6路由器 命令注入漏洞

文章目录 1.漏洞描述 2.环境搭建 3.漏洞复现 4.漏洞分析 4.1&#xff1a;代码分析  4.2&#xff1a;流量分析 5.poc代码&#xff1a; 1.漏洞描述 漏洞编号&#xff1a;CVE-2022-35555 漏洞名称&#xff1a;Tenda W6 命令注入 威胁等级&#xff1a;高危 漏洞详情&#xff1…...

算法分析 ——《模拟》

文章目录 《替换所有的问号》题目描述&#xff1a;代码演示&#xff1a;代码解析&#xff1a; 《提莫攻击》题目描述&#xff1a;代码演示&#xff1a;代码解析&#xff1a; [《Z 字形变换》](https://leetcode.cn/problems/zigzag-conversion/)题目描述&#xff1a;代码演示&a…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...