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 中插槽的几种常见用法: 默认插槽 默认插槽是最基本的插槽类型࿰…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
