1 两数之和
解题思路:
\qquad 对每个数nums[i]
,仅需在数组中搜索target-nums[i]
是否存在。
优化思路:
\qquad 首先能想到,利用哈希表O(1)
查询target-nums[i]
。
\qquad 建立map<int, vector<int>>
的表能够处理重复元素,保证找到所有解。但是,能否进一步优化?
\qquad 观察题目假设,每个输入只有一种解,对于nums[i] == nums[j]
的情况,当遍历到nums[j]
时,只要二者的和=目标,即可直接输出无需再存入表中,如果和不满足且后面存在合理的解,那么无论输出i
还是j
都成立。所以建立的表无需处理重复的情况,可建表map<int,int>
。
\qquad 到这里,思路已经足够简洁,但是能否进一步优化代码实现提高运行速度?
优化代码:
\qquad 1)使用unordered_map
。
map | unordered_map | |
---|---|---|
特点 | 有顺序(key升序) | 元素排列无顺序 |
实现方式 | 红黑树 | 哈希表(散列表) |
时间效率 | O(logn) | O(1) |
存储效率 | 接近100% | 表中存在未使用的值 |
稳定性分析 | 平衡二叉树,十分稳定O(logn) | 不稳定,最快O(1),最坏O(n)【冲突过多时】 |
头文件 | <map> | <unordered_map> |
\qquad 注:写题大多时候适用 unordered_map,当对查询稳定性要求高、需要排序时用map。
\qquad 2)虽然函数返回值为vector<int>
,但已知返回长度,可以不建立数组,直接返回{num1,num2}
。
vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> m;int n = nums.size();for(int i = 0; i < n; i++){if(m.count(target - nums[i]) == 0){m[nums[i]] = i;}else{return {i, m[target - nums[i]]};}}return {};}
参考博客:
https://blog.csdn.net/JCjunior/article/details/107471425
https://blog.csdn.net/qq_45890970/article/details/123955261
相关文章:

1 两数之和
解题思路: \qquad 对每个数nums[i],仅需在数组中搜索target-nums[i]是否存在。 优化思路: \qquad 首先能想到,利用哈希表O(1)查询target-nums[i]。 \qquad 建立map<int, vector<int>>的表能够处理重复元素&#x…...

NewStarCTF2023week2-Unserialize?
代码审计: 定义了一个eval类,该类下有一个私有变量cmd和公有成员函数destruct(),该函数在对象的所有引用都被删除或类被销毁时会自动调用; 调用该函数则会执行一个正则表达式进行正则匹配,过滤掉了一些常用命令和bas…...
OpenMesh 最优选点策略
文章目录 一、简介二、实现代码三、实现效果参考文献一、简介 继续沿着之前的思路:OpenMesh 网格顶点Quadric误差计算,有时候,无论是网格简化或是网格平滑,总会涉及到添加一个新的顶点的问题,那么新顶点应该怎么生成呢?以网格的简化操作为例,假设我们要合并两个顶点,也…...
服务器内存总量和内存条有差异是什么问题 103.239.244.X
服务器内存总量和内存条上标注的容量可能会存在一些差异,这是由于以下几个原因: 部分内存被保留给系统和其他硬件设备:在服务器中,一部分内存可能被保留给系统和其他硬件设备,比如显卡、网卡、RAID卡等。这些设备需要一…...

WPF DataGrid详细列表手动显示与隐藏
设置显示序号与折叠显示样式 <DataTemplate x:Key"dtNum"><Button BorderBrush"Transparent" Style"{x:Null}" Click"BtnRowDetail_ShowHideClick" FontSize"16" Background"Transparent"><Stack…...

Compose 组件 - 分页器 HorizontalPager、VerticalPager
一、概念 类似于 ViewPager,1.4 版本之前需要借助 accompanis 库,底层基于 LazyColumn、LazyRow 实现,在使用上也基本相同。默认情况下 HorizontalPager 占据屏幕的整个宽度,VerticalPager 会占据整个高度。 fun HorizontalPager(…...

Web3 招聘 | Bitget、MyShell、imToken、Arweave 多项目招聘中
「Web3 招聘」是 TinTinLand 为 Web3 项目和求职者创建的一个招聘信息汇集专栏。本栏目将持续更新区块链行业招聘信息,满足不同求职者与项目方的多样需求。欢迎各项目方联系 TinTinLand 发布职位需求,欢迎求职者关注 TinTinLand 获取最新招聘信息。 此外…...

通过HTTP发送大量数据的三种方法
在网络的早期时期,人们发送的文件大小仅为几KB。到了2023年,我们享受着高分辨率的MB级别图像,并在几GB的4K(即将是8K)视频中观看。 即使有良好的互联网连接,下载一个5GB的文件仍然需要一些时间。如果你拥有…...
【MySQL】索引和事物
目录 ♫索引 ♪什么是索引 ♪索引的数据结构 ♪索引的使用 ♫事务 ♪什么是事务 ♪事务的特性 ♪事务的使用 ♫索引 ♪什么是索引 索引是存储在磁盘上的一个数据结构,通过索引可以快速地定位到存储在磁盘上的数据。 索引在提高查询速度的同时,还提…...

win11下的VS2022+QT6+VTK9.2+PCL1.13.1联合开发环境配置及踩坑记录
准备工作: 安装VS2022:这个比较简单,网上随便找个教程就行 安装QT并为VS2022添加QT Creater插件:VS2022配置Qt6_vs2022 qt6-CSDN博客 安装PCL:vs2022配置pcl1.13.1_pcl配置-CSDN博客 安装PCL过程中本身也会安装VTK&…...
CEdit
1、https://www.cnblogs.com/milanleon/p/5626174.html 2、CEdit控件提供访问函数主要有: int GetWindowText(LPCTSTR lpszStringBuf,intnMaxCount) 获取控件文本,与ReadText()功能相同 void SetWindowText(LPCTSTR lpszString) 设置控件文本 void …...

vue3 自定义指令
Vue 除了内置的一系列指令 (比如 v-model 或 v-show) 之外,Vue 还允许你注册自定义的指令。 一个自定义指令由一个包含类似组件生命周期钩子的对象来定义。钩子函数会接收到指令所绑定元素作为其参数。 在setup语法糖中,任何以 v 开头的驼峰式命名的变量…...
用PolarDB|PostgreSQL提升通用ai机器人在专业领域的精准度
目录 背景 基本步骤讲解 Demo 演示 思考 如果不是用openai? 开源社区能干点啥? ai应用 收录专栏:PolarDB for PostgreSQL,后续将会发布PolarDB for PostgreSQL教程,大家感兴趣的话可以点个订阅呀! 简介: chat…...

idea中maven plugin提示not found
在终端中输入: mvn dependency:resolve 然后 解决了部分问题 Plugin org.apache.maven.plugins:maven-jar-plugin:3.1.0 not found 改为3.3.0了 Plugin maven-source-plugin:3.3.0 not found 改为 2.4 了 版本下降了 感觉后继有坑 待观察...

Hadoop3教程(七):MapReduce概述
文章目录 (68) MR的概述&优缺点(69)MR的核心思想MapReduce进程 (70)官方WC源码&序列化类型(71)MR的编程规范MapperReducerDriver (72)WordCount案例需…...
【Doris实战】Apache-doris-2.0.2部署帮助手册
Apache-doris-2.0.2部署帮助手册 校验时间:2023年10月11日 文章目录 Apache-doris-2.0.2部署帮助手册安装前准备安装包安装要求Linux 操作系统版本需求软件需求句柄需求关闭 Swap网络需求 部署规划用户规划目录规划免密需求 安装步骤配置JDK配置Doris文件 启动与停止…...
如何处理接口调用的频率限制
背景 接口提供方有调用频率限制的场景下,如何合理设计接口请求? 方案 采用Redis队列,利用 lpush 和 rpop 命令来实现 首先,将订单依次lpush写入Redis队列。定时任务通过 rpop 获取队列订单进行接口调用。 额外说明: 若想查看…...
Ubuntu 22.04上安装Anaconda,及 conda 的基础使用
1. 安装软件依赖包: apt install libgl1-mesa-glx libegl1-mesa libxrandr2 libxrandr2 libxss1 libxcursor1 libxcomposite1 libasound2 libxi6 libxtst6 2. 下载Anaconda安装包 使用 wget下载您从Anaconda网站复制的链接。您将把它输出到一个名为anaconda.sh的文…...

算法练习13——跳跃游戏II
LeetCode 45 跳跃游戏 II 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i j] 处: 0 < j < nums[i] i j < n 返回…...
算法|每日一题|只出现一次的数字|位运算
136.只出现一次的数字 力扣每日一题:136.只出现一次的数字 之前整理过本题及其扩展,详细说明了思路和做法,链接如下: 只出现一次的数字I,II,III 给你一个 非空 整数数组 nums ,除了某个元素只出…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...

对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...