leetcode 面试经典 150 题:两数之和
链接 | 两数之和 |
---|---|
题序号 | 1 |
题型 | 数组 |
解题方法 | 1. 哈希表,2. 暴力法 |
难度 | 简单 |
熟练度 | ✅✅✅✅✅ |
题目
给定一个整数数组 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 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案进阶:
你可以想出一个时间复杂度小于 O(n2) 的算法吗?
题解
-
核心思想:
- 使用一个哈希表来存储数组元素及其对应的下标。键是数组元素,值是元素的下标。
- 遍历数组,对于每个元素 nums[i],计算 complement = target - nums[i]。
- 检查 complement 是否在哈希表中。如果在,说明找到了两个数,它们的和为 target,直接返回它们的下标;如果不在,将当前元素 nums[i] 及其下标 i 存入哈希表。
-
复杂度:时间复杂度O(N),空间复杂度O(N)。
-
c++ 实现算法:
vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> numMap; // 用于存储数字和它的索引//遍历数组 nums,从索引 i = 0 开始,直到数组的最后一个元素for (int i = 0; i < nums.size(); ++i) {int complement = target - nums[i]; // 计算当前数字需要的补数//检查哈希表中是否存在补数 complement。如果找到了,表示我们已经找到了一对数字,//它们的和为 target。find 函数用于查找哈希表中是否存在给定的键(complement)。//如果存在,find 会返回一个指向该元素的迭代器,否则返回 end()。if (numMap.find(complement) != numMap.end()) {return {numMap[complement], i}; // 返回补数的索引和当前数字的索引,找到了就直接返回不需要继续找了}//它的键是数组中的元素,值是该元素的索引。//通过 numMap[nums[i]] = i,我们将当前元素 nums[i] 的值作为键,将其索引 i 作为值存储在哈希表中。numMap[nums[i]] = i; }return {}; // 如果没有找到符合条件的结果,返回空数组
}
- 算法推演:
假设输入数组 nums = [2, 7, 11, 15] 和目标值 target = 9。
步骤 1:初始化哈希表
unordered_map<int, int> numMap; 这里创建了一个哈希表 numMap,它的键(key)是数组中的元素,值(value)是该元素的索引。哈希表的作用是快速查找数组中是否已经存在与当前数字相加等于目标值的数字。步骤 2:遍历数组
我们开始遍历数组 nums。
- 第一次迭代(i = 0,nums[i] = 2):
计算补数:complement = target - nums[0] = 9 - 2 =7。
检查哈希表中是否有 complement = 7: numMap.find(7) 返回 numMap.end(),表示没有找到补数。
将 nums[0] = 2 和它的索引 0 存入哈希表:numMap[2] = 0。
当前哈希表状态:numMap = {2: 0}。- 第二次迭代(i = 1,nums[i] = 7):
计算补数:complement = target - nums[1] = 9 - 7 = 2。
检查哈希表中是否有 complement = 2: numMap.find(2) 返回 numMap[2] = 0,表示找到了补数
2,它的索引是 0。
找到符合条件的两个数字:nums[0] = 2 和 nums[1] = 7,它们的和是 9。
返回这两个索引:return {numMap[2], 1},即返回 [0, 1]。
- c++ 完整 demo:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> numMap; // 用于存储数字和它的索引//遍历数组 nums,从索引 i = 0 开始,直到数组的最后一个元素for (int i = 0; i < nums.size(); ++i) {int complement = target - nums[i]; // 计算当前数字需要的补数//检查哈希表中是否存在补数 complement。如果找到了,表示我们已经找到了一对数字,//它们的和为 target。find 函数用于查找哈希表中是否存在给定的键(complement)。//如果存在,find 会返回一个指向该元素的迭代器,否则返回 end()。if (numMap.find(complement) != numMap.end()) {return {numMap[complement], i}; // 返回补数的索引和当前数字的索引,找到了就直接返回不需要继续找了}//它的键是数组中的元素,值是该元素的索引。//通过 numMap[nums[i]] = i,我们将当前元素 nums[i] 的值作为键,将其索引 i 作为值存储在哈希表中。numMap[nums[i]] = i; }return {}; // 如果没有找到符合条件的结果,返回空数组
}int main() {vector<int> nums = {2, 7, 11, 15};int target = 9;vector<int> result = twoSum(nums, target);if (!result.empty()) {cout << "Indices: " << result[0] << ", " << result[1] << endl;} else {cout << "No solution found!" << endl;}return 0;
}
相关文章:
leetcode 面试经典 150 题:两数之和
链接两数之和题序号1题型数组解题方法1. 哈希表,2. 暴力法难度简单熟练度✅✅✅✅✅ 题目 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输…...

nexus搭建maven私服
说到maven私服每个公司都有,比如我上一篇文章介绍的自定义日志starter,就可以上传到maven私服供大家使用,每次更新只需deploy一下就行,以下就是本人搭建私服的步骤 使用docker安装nexus #拉取镜像 docker pull sonatype/nexus3:…...

理解 Tomcat 架构
前言 Tomcat 是一个轻量级的 Web 容器,被广泛应用于 Java Web 开发中。通过它,我们可以轻松地部署和运行 Web 应用。在本文中,我们将深入分析 Tomcat 的核心架构,同时结合一段代码,手动实现一个简化的 Tomcat 服务&am…...

python3GUI--大屏可视化-传染病督导平台 By:PyQt5
文章目录 一.前言二.预览三.软件组成&开发心得1.样式&使用方法2.左侧表格实现3.设计4.学习5.体验效果 四.代码分享1.环形渐变进度组件2.自定义图片的背景组件 五.总结 大小:60.9 M,软件…...

如何选择适合的证件照制作软件,让您的照片制作更轻松
在当今数字化的时代,制作证件照不再需要专门前往照相馆。选择一款合适的证件照制作软件,您可以在家中轻松完成标准证件照的拍摄与制作。然而,面对市面上琳琅满目的软件,找到最适合您需求的软件并不简单。本文将为您详细介绍选择证…...
工作效率提升:使用Anaconda Prompt 创建虚拟环境总结
目录 完整顺序命令流程(直接照着改就行)详细步骤解析(想要详细解析的看过来)1. 创建一个用于存储 Conda 环境的目录(可选)2. 创建新的 Conda 虚拟环境并指定路径3. 激活新创建的环境4. 安装 Jupyter Notebo…...

Python自动化实战 —— 使用Selenium进行Web自动化
为了完成一项重复的任务,你需要在网站上进行大量的点击和操作,每次都要浪费大量的时间和精力。Python的Selenium库就可以自动化完成这些任务。 在本篇文章中,我们将会介绍如何使用Python的Selenium库进行Web自动化,以及如何将它应…...

【前端】【HTML】入门基础知识
参考视频:【狂神说Java】HTML5完整教学通俗易懂_哔哩哔哩_bilibili 一、基本结构 二、基本标签 <h1>:一级标题,通常用于页面的主标题,字体较大且醒目。 <h2>:二级标题,用于副标题或主要章节标…...
PHP获取局域网ip(192.168)
有时候,程序中,需要获取本机内网ip的情况,经过各种资料查找,最终确定一下代码: //获取内网ipfunction getLocalIP() {exec("ipconfig /all",$arr);$res mb_convert_encoding($arr, UTF-8, GBK);$ip ;fore…...

点击底部的 tabBar 属于 wx.switchTab 跳转方式,目标页面的 onLoad 不会触发(除非是第一次加载)
文章目录 1. tabBar 的跳转方式2. tabBar 跳转的特点3. 你的配置分析4. 生命周期触发情况5. 总结 很多人不明白什么是第一次加载,两种情况讨论,第一种情况假设我是开发者,第一次加载就是指点击微信开发者工具上边的编译按钮,每点击…...
基于PLC的酒店热水供应控制系统设计
摘 要 酒店的热水量需求比较大,热水加热消耗能源比较多,为了实现清洁能源加热实现热水供应,系统设计以太阳能作为主要能源来源,以电加热作为辅助能源来源进行系统的设计.通过集热器、储水箱、循环泵等设备组成酒店热水供水系统。通过控制温度传感器的信号,实现恒温…...

博客内所有项目均可在面包多平台进行购买
本人已入住面包多平台:我的 - 面包多 已有资料:...

《Mcal》--MCU模块
一、MCU模块的主要功能 控制系统时钟的产生。控制系统通用模块,该模块会涉及到Adc、Ftm等外设的配置。控制外设时钟。控制MCU运行的模式。初始化定义RAM Section。 比较重要的是时钟的配置。 二、系统时钟的配置 1、芯片时钟树 要想弄明白时钟配置,需…...

C语言:枚举类型
一、枚举类型的声明 枚举顾名思义就是一一列举。我们可以把可能的取值一一列举。比如我们现实生活中: 星期一到星期日是有限的7天,可以一一列举 ;性别有:男、女、保密,也可以一一列举 ;月份有12个月&#x…...

spring boot 多数据源集成mysql、postgresql、phoenix、doris等
如何搭建多数据源项目只要以下简单几步; 一. 创建核心在config.datasource文件夹里 二. 引入相对应的jar包 三. 创建数据库连接配置 四. 写逻辑代码进行验证 1.DataSource package com.irootech.config.datasource;import java.lang.annotation.*;Target({ElementType.MET…...
USB基础 -- USB 控制传输(Control Transfer)的重传机制
USB 控制传输(Control Transfer)的重传机制 1. 控制传输的事务结构 控制传输分为三个阶段,每个阶段都有自己的事务,并可能触发重传机制: 设置阶段(Setup Stage):主机发送 8 字节的…...

云计算基础,虚拟化原理
文章目录 一、虚拟化1.1 什么是虚拟化1.2 虚拟化类型 二 、存储虚拟化2.1 存储指标2.2 存储类型2.3 存储协议2.4 RAID 三、内存 i/O虚拟化3.1 内存虚拟化基本概念地址空间转换原理内存共享与隔离原理 3.2 I/O 虚拟化基本概念模拟(Emulation)方式半虚拟化…...
浮点数在C语言开发中为什么不精确?
在C语言开发中,浮点数的精度问题是一个常见的陷阱,尤其是对于刚接触编程的开发者来说,可能会对浮点数的行为感到困惑。为什么0.1 0.2不等于0.3?为什么浮点数计算会出现微小误差?本文将从计算机底层原理出发࿰…...
ChatGPT网络错误如何解决
在当今的信息化社会,网络技术已无处不在。无论是日常生活中的在线购物,还是工作中的远程会议,网络的稳定性和可靠性成为了我们无时无刻不在关注的重要问题。而在智能技术的快速发展中,像ChatGPT这样的人工智能模型,因其…...

Vue3初学之插槽(slot)使用
在 Vue 3 中,插槽(Slots)是一种强大的内容分发机制,允许你在组件中定义可替换的内容区域,从而使组件更加通用和灵活。以下是 Vue 3 中插槽的几种常见用法: 默认插槽 默认插槽是最基本的插槽类型࿰…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...

ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...