Leetcode100-两数之和
参见官方题解
一、学到的知识
-
正面寻找两个数之和相加等于某个数,如 a+b = c,不如反过来寻找 a = c - b
正面寻找需要两层 for 循环,把每个数都进行遍历,所以时间复杂度较高
反过来则可以通过维护一个 a 的集合,每次通过查询 c - b 是否在集合中,判断是否存在 a = c - b
存在,则返回答案;不存在,则将 a 插入集合中, 待下次查询
-
想一下,我们为什么把 a 插入集合中,而不是 c - b呢?
如果把 c - b 插入集合,意味着我们将判断 a 是否在集合中,总之就是要判断是否存在 a = c - b,两者写法其实都可以
二、代码
-
版本1
时间复杂度 O(N)
空间复杂度 O(1)比较好想到的一个方法是先使用一层 for 循环枚举 a,再使用一层 for 循环枚举 b,判断 a + b == c 是否为真即可
而且也容易想到一点优化,对于位于 x 位置的元素,1…x-1次循环的时候,nums[x]已经被匹配过,所以无需再匹配,所以在代码中,可以看到,第二层枚举 b 的循环,从 i + 1 开始class Solution { public:vector<int> twoSum(vector<int>& nums, int target){const int Size = nums.size();for (int i = 0; i < Size; ++i){for (int j = i + 1; j < Size; ++j){if (nums[i] + nums[j] == target){return {i, j};}}}return {0, 0};} }; -
版本2
时间复杂度 O(NlogN)
空间复杂度 O(N)这是版本1的优化, 前文提过,需要寻找 a + b = c,我们可以把 b 移至右侧,寻找 a = c - b,我们很自然的想到,可以维护一个数的集合,再从中寻找元素是否存在
而这个集合的查找的复杂度,就决定了我们算法的复杂度,在代码中,我们使用了标准库中的 map,它的查找效率是 LogN
class Solution { public:std::vector<int> twoSum(std::vector<int>& nums, int target){const int size = nums.size();map<int, int> Map;for (int i = 0; i < size; ++i){const int gap = target - nums[i];auto iterator = Map.find(gap);if (iterator != Map.end()){return {iterator->second, i};}Map.insert({nums[i], i});}return {-1, -1};} };
相关文章:
Leetcode100-两数之和
参见官方题解 一、学到的知识 正面寻找两个数之和相加等于某个数,如 ab c,不如反过来寻找 a c - b 正面寻找需要两层 for 循环,把每个数都进行遍历,所以时间复杂度较高 反过来则可以通过维护一个 a 的集合,每次通过…...
4565: 删除中间的*
描述规定输入的字符串中只包含字母和*号,除了字符串前导和尾部的*号之外,将串中其他*号全部删除输入输入数据包括一串字符串,只包含字母和*,总长度不超过80。输出输出删除中间*后的字符串。样例输入*******A*BC*DEF*G****样例输出*******ABCD…...
VUE组件示例说明
<!-- * Author: xxx.xx * Date: 2021-07-20 14:33:41 * LastEditors: xxx.xx * LastEditTime: 2021-07-20 18:22:37 * PageTitle: 上拉加载组件 * Description: 描述... * FilePath: /wxapp-view/components/loadmore.vue --> <template><view class"c-mor…...
Widget中的State-学习笔记
Widget 有 StatelessWidget 和 StatefulWidget 两种类型。StatefulWidget 应对有交互、需要动态变化视觉效果的场景,而 StatelessWidget 则用于处理静态的、无状态的视图展示。StatefulWidget 的场景已经完全覆盖了 StatelessWidget,因此我们在构建界面时…...
股市实战技巧(知行合一)
投资策略 长线:优质核心股票大仓位核心标的票,小仓位短线投资投机小储蓄可加大投机仓位价值投资也要去做仓位控制 行情好,总体大仓位,行情小,小仓位个股根据走势调整个股仓位(布林线的20%原则)…...
k8s-资源限制-探针检查
文章目录一、资源限制1、资源限制的使用2、reuqest资源(请求)和limit资源(约束)3、Pod和容器的资源请求和限制4、官方文档示例5、资源限制实操5.1 编写yaml资源配置清单5.2 释放内存(node节点,以node01为例…...
一文让你彻底了解Linux内核文件系统
一,文件系统特点 文件系统要有严格的组织形式,使得文件能够以块为单位进行存储。文件系统中也要有索引区,用来方便查找一个文件分成的多个块都存放在了什么位置。如果文件系统中有的文件是热点文件,近期经常被读取和写入…...
解决前端组件下拉框选择功能失效问题
问题: 页面下拉框选择功能失效 现象: 在下拉框有默认值的情况下,点击下拉框的其他值,发现并没有切换到其他值 但是在下拉框没默认值的情况下,功能就正常 原因 select 已经绑定选项(有默认值) 在…...
Linux_vim编辑器入门级详细教程
前言(1)vim编辑器其实本质上就是对文本进行编辑,比如在.c文件中改写程序,在.txt文件写笔记什么的。一般来说,我们可以在windows上对文本进行编译,然后上传给Linux。但是有时候我们可能只是对文本进行简单的…...
TCP 的演化史-TCP 是一个过渡
TCP 诞生于 1970 年代早期,彼时没有分组交换网的大规模应用,彼时绝大多数通信都在使用电话,电报,电挂等电路交换技术。 诞生在这种环境下的技术不可能脱离时代的影响,如果一个孩子出生在一个父母关系冷漠的家庭&#x…...
Flask
Flask第三方组件非常全,适合小型 API服务类项目,但第三方组件运行稳定性相对Django差。 基础知识 Flask安装 pip install flask2.0.3Flask库文件 Jinjia2:模板渲染库Markupsafe:返回安全标签 只要Flask返回模板或者标签时都会…...
SAP系统与MES系统的数据协同技术方案
1.MES介绍 本文中提到的MES系统是在西门子公司的SIMATIC IT平台上开发完成。所有的应用子系统进行统一分析、统一设计、统一开发,利用统一的开发平台和数据库系统,保证了管理系统的集成性、高效性。 2.数据协同接口包含的…...
2018年蓝桥杯省赛试题-5道(Python)
文章目录一、日志统计思考二、递增三元组思考三、螺旋折线思考四、乘积最大思考五、全球变暖思考尾声提示:以下是本篇文章正文内容,下面案例可供参考 一、日志统计 题目描述 小明维护着一个程序员论坛。 现在他收集了一份"点赞"日志…...
Python稀疏矩阵最小二乘法
文章目录最小二乘法返回值测试最小二乘法 scipy.sparse.linalg实现了两种稀疏矩阵最小二乘法lsqr和lsmr,前者是经典算法,后者来自斯坦福优化实验室,据称可以比lsqr更快收敛。 这两个函数可以求解AxbAxbAxb,或arg minx∥Ax−b…...
mac本前端Homebrew下载,操作
1、打开电脑终端 2、下载Homebrew,在终端中输入 /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"开始下载Homebrew,因为这个地址是国外网站,下载失败的话,输入…...
Linux系统之查看进程监听端口方法
Linux系统之查看进程监听端口方法一、端口监听介绍二、使用netstat命令1.netstat命令介绍2.netstat帮助3.安装netstat工具4.列出所有监听 tcp 端口5.显示TCP端口的统计信息6.查看某个服务监听端口三、使用ss命令1.ss命令介绍2.ss命令帮助3.查看某个服务监听端口四、使用lsof命令…...
使用命令别名一键启动arthas
1. 使用命令别名启动arthas 确保单板上有jdk和arthas jdk目录:/home/xinliushijian/arthas/jdk arthas目录;/home/xinliushijian/arthas su xinliushijian编写脚本messi.sh cd /home/xinliushijian/arthas vi messi.sh 内容如下: #!/bin/ba…...
python+pytest接口自动化(2)-HTTP协议基础
HTTP协议简介HTTP 即 HyperText Transfer Protocol(超文本传输协议),是互联网上应用最为广泛的一种网络协议。所有的 WWW 文件都必须遵守这个标准。设计 HTTP 最初的目的是为了提供一种发布和接收 HTML 页面的方法。HTTP 协议在 OSI 模型中属…...
操作系统权限提升(十五)之绕过UAC提权-基于白名单DLL劫持绕过UAC提权
系列文章 操作系统权限提升(十二)之绕过UAC提权-Windows UAC概述 操作系统权限提升(十三)之绕过UAC提权-MSF和CS绕过UAC提权 操作系统权限提升(十四)之绕过UAC提权-基于白名单AutoElevate绕过UAC提权 注:阅读本编文章前,请先阅读系列文章,以…...
非常好看的html网页个人简历
一. 前言 文末获取gitee链接 在前几天逛b站的时候,发现了个比较实用的东西-----个人简介网页版,相当于网页版的个人简历,相较于PDF形式的,网页版所能呈现内容更加丰富,而且更加美观,在BOOS上被HR小姐姐要…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...
32单片机——基本定时器
STM32F103有众多的定时器,其中包括2个基本定时器(TIM6和TIM7)、4个通用定时器(TIM2~TIM5)、2个高级控制定时器(TIM1和TIM8),这些定时器彼此完全独立,不共享任何资源 1、定…...
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑 在电子商务领域,转化率与网站性能是决定商业成败的核心指标。今天,我们将深入解析不同类型电商平台的转化率基准,探讨页面加载速度对用户行为的…...
Pandas 可视化集成:数据科学家的高效绘图指南
为什么选择 Pandas 进行数据可视化? 在数据科学和分析领域,可视化是理解数据、发现模式和传达见解的关键步骤。Python 生态系统提供了多种可视化工具,如 Matplotlib、Seaborn、Plotly 等,但 Pandas 内置的可视化功能因其与数据结…...
7种分类数据编码技术详解:从原理到实战
在数据分析和机器学习领域,分类数据(Categorical Data)的处理是一个基础但至关重要的环节。分类数据指的是由有限数量的离散值组成的数据类型,如性别(男/女)、颜色(红/绿/蓝)或产品类…...
