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

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) 的算法吗?

题解

  1. 核心思想

    • 使用一个哈希表来存储数组元素及其对应的下标。键是数组元素,值是元素的下标。
    • 遍历数组,对于每个元素 nums[i],计算 complement = target - nums[i]。
    • 检查 complement 是否在哈希表中。如果在,说明找到了两个数,它们的和为 target,直接返回它们的下标;如果不在,将当前元素 nums[i] 及其下标 i 存入哈希表。
  2. 复杂度:时间复杂度O(N),空间复杂度O(N)。

  3. 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 {}; // 如果没有找到符合条件的结果,返回空数组
}
  1. 算法推演
  • 假设输入数组 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]。
  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. 哈希表&#xff0c;2. 暴力法难度简单熟练度✅✅✅✅✅ 题目 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。 你可以假设每种输…...

nexus搭建maven私服

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

理解 Tomcat 架构

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

python3GUI--大屏可视化-传染病督导平台 By:PyQt5

文章目录 一&#xff0e;前言二&#xff0e;预览三&#xff0e;软件组成&开发心得1.样式&使用方法2.左侧表格实现3.设计4.学习5.体验效果 四&#xff0e;代码分享1.环形渐变进度组件2.自定义图片的背景组件 五&#xff0e;总结 大小&#xff1a;60.9 M&#xff0c;软件…...

如何选择适合的证件照制作软件,让您的照片制作更轻松

在当今数字化的时代&#xff0c;制作证件照不再需要专门前往照相馆。选择一款合适的证件照制作软件&#xff0c;您可以在家中轻松完成标准证件照的拍摄与制作。然而&#xff0c;面对市面上琳琅满目的软件&#xff0c;找到最适合您需求的软件并不简单。本文将为您详细介绍选择证…...

工作效率提升:使用Anaconda Prompt 创建虚拟环境总结

目录 完整顺序命令流程&#xff08;直接照着改就行&#xff09;详细步骤解析&#xff08;想要详细解析的看过来&#xff09;1. 创建一个用于存储 Conda 环境的目录&#xff08;可选&#xff09;2. 创建新的 Conda 虚拟环境并指定路径3. 激活新创建的环境4. 安装 Jupyter Notebo…...

Python自动化实战 —— 使用Selenium进行Web自动化

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

【前端】【HTML】入门基础知识

参考视频&#xff1a;【狂神说Java】HTML5完整教学通俗易懂_哔哩哔哩_bilibili 一、基本结构 二、基本标签 <h1>&#xff1a;一级标题&#xff0c;通常用于页面的主标题&#xff0c;字体较大且醒目。 <h2>&#xff1a;二级标题&#xff0c;用于副标题或主要章节标…...

PHP获取局域网ip(192.168)

有时候&#xff0c;程序中&#xff0c;需要获取本机内网ip的情况&#xff0c;经过各种资料查找&#xff0c;最终确定一下代码&#xff1a; //获取内网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. 总结 很多人不明白什么是第一次加载&#xff0c;两种情况讨论&#xff0c;第一种情况假设我是开发者&#xff0c;第一次加载就是指点击微信开发者工具上边的编译按钮&#xff0c;每点击…...

基于PLC的酒店热水供应控制系统设计

摘 要 酒店的热水量需求比较大,热水加热消耗能源比较多,为了实现清洁能源加热实现热水供应,系统设计以太阳能作为主要能源来源,以电加热作为辅助能源来源进行系统的设计.通过集热器、储水箱、循环泵等设备组成酒店热水供水系统。通过控制温度传感器的信号&#xff0c;实现恒温…...

博客内所有项目均可在面包多平台进行购买

本人已入住面包多平台&#xff1a;我的 - 面包多 已有资料&#xff1a;...

《Mcal》--MCU模块

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

C语言:枚举类型

一、枚举类型的声明 枚举顾名思义就是一一列举。我们可以把可能的取值一一列举。比如我们现实生活中&#xff1a; 星期一到星期日是有限的7天&#xff0c;可以一一列举 &#xff1b;性别有&#xff1a;男、女、保密&#xff0c;也可以一一列举 &#xff1b;月份有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 控制传输&#xff08;Control Transfer&#xff09;的重传机制 1. 控制传输的事务结构 控制传输分为三个阶段&#xff0c;每个阶段都有自己的事务&#xff0c;并可能触发重传机制&#xff1a; 设置阶段&#xff08;Setup Stage&#xff09;&#xff1a;主机发送 8 字节的…...

云计算基础,虚拟化原理

文章目录 一、虚拟化1.1 什么是虚拟化1.2 虚拟化类型 二 、存储虚拟化2.1 存储指标2.2 存储类型2.3 存储协议2.4 RAID 三、内存 i/O虚拟化3.1 内存虚拟化基本概念地址空间转换原理内存共享与隔离原理 3.2 I/O 虚拟化基本概念模拟&#xff08;Emulation&#xff09;方式半虚拟化…...

浮点数在C语言开发中为什么不精确?

在C语言开发中&#xff0c;浮点数的精度问题是一个常见的陷阱&#xff0c;尤其是对于刚接触编程的开发者来说&#xff0c;可能会对浮点数的行为感到困惑。为什么0.1 0.2不等于0.3&#xff1f;为什么浮点数计算会出现微小误差&#xff1f;本文将从计算机底层原理出发&#xff0…...

ChatGPT网络错误如何解决

在当今的信息化社会&#xff0c;网络技术已无处不在。无论是日常生活中的在线购物&#xff0c;还是工作中的远程会议&#xff0c;网络的稳定性和可靠性成为了我们无时无刻不在关注的重要问题。而在智能技术的快速发展中&#xff0c;像ChatGPT这样的人工智能模型&#xff0c;因其…...

Vue3初学之插槽(slot)使用

在 Vue 3 中&#xff0c;插槽&#xff08;Slots&#xff09;是一种强大的内容分发机制&#xff0c;允许你在组件中定义可替换的内容区域&#xff0c;从而使组件更加通用和灵活。以下是 Vue 3 中插槽的几种常见用法&#xff1a; 默认插槽 默认插槽是最基本的插槽类型&#xff0…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

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

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

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...