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

Leetcode算法系列| 1. 两数之和(四种解法)

目录

  • 1.题目
  • 2.题解
    • 解法一:暴力枚举
    • 解法二:哈希表解法
    • 解法三:双指针(有序状态)
    • 解法四:二分查找(有序状态)

1.题目

给定一个整数数组 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
只会存在一个有效答案

2.题解

解法一:暴力枚举

最容易想到的方法是枚举数组中的每一个数 x,寻找数组中是否存在 target - x。
当我们使用遍历整个数组的方式寻找 target - x 时,需要注意到每一个位于 x 之前的元素都已经和 x 匹配过,因此不需要再进行匹配。而每一个元素不能被使用两次,所以我们只需要在 x 后面的元素中寻找 target - x。

    public int[] TwoSum(int[] nums, int target){int n=nums.Length;for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){if (nums[i] + nums[j] == target){return new int[] { i, j };}}}return new int[] { 0, 0 };}

1

  • 时间复杂度: O(n^2) ,空间复杂度: O(1)

解法二:哈希表解法

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。
使用哈希表,可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。
这样我们创建一个哈希表,对于每一个 x,我们首先查询哈希表中是否存在 target - x,然后将 x 插入到哈希表中,即可保证不会让 x 和自己匹配。

   public int[] TwoSum(int[] nums, int target) {Dictionary<int, int> twoSum = new Dictionary<int, int>();for (int i = 0; i < nums.Length; i++){if(twoSum.ContainsKey(target-nums[i])){return new int[] {twoSum[target - nums[i]], i};}else    {twoSum[nums[i]] = i;}}return new int[] {0, 0};}

2

  • 时间复杂度:O(n),空间复杂度:O(n)。

解法三:双指针(有序状态)

    public int[] towSum(int[] nums, int target){int left = 0;int right = nums.Length - 1;for (int i = 0; i < nums.Length; i++){if (nums[left] + nums[right] > target){right--;}else if (nums[left] + nums[right] < target){left++;}else{return new int[] { left, right };}}return new int[] { };}
  • 时间复杂度:O(nlogn),空间复杂度:O(n)。

解法四:二分查找(有序状态)

 public int[] towSum(int[] nums, int target){for (int i = 0; i < nums.Length; i++){int low = i + 1;int high = nums.Length - 1;while (low <= high){int mid = (high - low) / 2 + low;if (nums[mid] > target - nums[i]){high = mid - 1;}else if (nums[mid] < target - nums[i]){low = mid + 1;}else{return new int[] { i, mid };}}}return new int[] { };}
  • 时间复杂度:O(nlogn),空间复杂度:O(n)。

相关文章:

Leetcode算法系列| 1. 两数之和(四种解法)

目录 1.题目2.题解解法一&#xff1a;暴力枚举解法二&#xff1a;哈希表解法解法三&#xff1a;双指针(有序状态)解法四&#xff1a;二分查找(有序状态) 1.题目 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数…...

汇编-pop出栈指令

32位汇编 执行动作分为两步&#xff1a; 第一步&#xff1a;读出数据 第二步&#xff1a;改变栈地址 如果操作数是16位&#xff0c; 则ESP加2&#xff1b; 如果操作数是32位&#xff0c; 则ESP加4 espesp2 或 espesp4 格式&#xff1a;...

【代码】基于VMD(变分模态分解)-SSA(麻雀搜索算法优化)-LSTM的光伏功率预测模型(完美复现)matlab代码

程序名称&#xff1a;基于VMD&#xff08;变分模态分解&#xff09;-SSA&#xff08;麻雀搜索算法优化&#xff09;-LSTM的光伏功率预测模型 实现平台&#xff1a;matlab 代码简介&#xff1a;提出了变分模态分解(VMD)和麻雀搜索算法(SSA)与长短期记忆神经网络 (LSTM)相耦合,…...

【UnLua】在 Lua 中定义 UE 反射类型

【UnLua】在 Lua 中定义 UE 反射类型 用法 启动编辑器时遍历 Defines 目录下 lua 脚本来加载 UE 反射类型&#xff08;开个临时的 Lua VM 即可&#xff09;直接像 -- define a uenum in lua UEnum.EEnumGuestSomethingElse {Value1 1;Value2 2; }-- use it like a native …...

react的开发中关于图片的知识

React是一个流行的JavaScript库&#xff0c;用于构建用户界面。在React开发中&#xff0c;图片是一个非常重要的元素&#xff0c;可以用于美化界面和展示内容。本篇博客将详细讲解React中关于图片的知识。 1. React中使用图片 在React中使用图片非常简单&#xff0c;只需要使…...

AcWing 188:武士风度的牛 ← BFS

【题目来源】https://www.acwing.com/problem/content/190/ 【题目描述】 农民 John 有很多牛&#xff0c;他想交易其中一头被 Don 称为 The Knight 的牛。 这头牛有一个独一无二的超能力&#xff0c;在农场里像 Knight 一样地跳&#xff08;就是我们熟悉的象棋中马的走法&…...

马养殖场建设VR模拟实训教学平台具有灵活性和复用性

为保障养殖场生物安全&#xff0c;避免疫病传播&#xff0c;学生出入养殖场受时间和地域的限制&#xff0c; 生产实习多以参观为主&#xff0c;通过畜牧企业技术人员的讲解&#xff0c;学生被动了解生产过程。为了解决畜牧养殖实训难的问题&#xff0c;借助VR技术开展畜牧养殖虚…...

云原生技术演进之路-(云技术如何一步步演进的,云原生解决了什么问题?)

云技术如何一步步演进的&#xff1f; 云原生解决了什么问题&#xff1f; 物理设备 电脑刚被发明的时候&#xff0c;还没有网络&#xff0c;每个电脑&#xff08;PC&#xff09;&#xff0c;就是一个单机。 这台单机&#xff0c;包括CPU、内存、硬盘、显卡等硬件。用户在单机…...

基于OGG实现Oracle实时同步MySQL

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…...

〖大前端 - 基础入门三大核心之JS篇㊷〗- DOM事件对象及它的属性

说明&#xff1a;该文属于 大前端全栈架构白宝书专栏&#xff0c;目前阶段免费&#xff0c;如需要项目实战或者是体系化资源&#xff0c;文末名片加V&#xff01;作者&#xff1a;不渴望力量的哈士奇(哈哥)&#xff0c;十余年工作经验, 从事过全栈研发、产品经理等工作&#xf…...

如何搭建zerotier服务器组网实现内网穿透

小白花了四天的下班时间终于把zerotier网络调通&#xff0c;此刻坐在桌前舒畅地喝口茶&#xff5e;&#xff5e; 下面来详细记录下这几天踩的坑&#xff1a; 起因就在于一直在iPad上用向日葵连接公司电脑的我觉得向日葵的界面用的实在难受&#xff0c;vs code操作十分不灵光&…...

【C++】构造函数和析构函数第四部分(深拷贝和浅拷贝)--- 2023.11.25

目录 什么是浅拷贝&#xff1f;浅拷贝的问题使用深拷贝解决浅拷贝问题结束语 什么是浅拷贝&#xff1f; 如果在一个类中没有人为定义拷贝函数&#xff0c;则系统会提供默认拷贝函数。那么在此默认拷贝函数中主要进行了简单的赋值操作&#xff0c;那这个简单的赋值操作我们一般…...

加速软件开发:自动化测试在持续集成中的重要作用!

持续集成的自动化测试 如今互联网软件的开发、测试和发布&#xff0c;已经形成了一套非常标准的流程&#xff0c;最重要的组成部分就是持续集成&#xff08;Continuous integration&#xff0c;简称CI&#xff0c;目前主要的持续集成系统是Jenkins&#xff09;。 那么什么是持…...

工具及方法 - 查找排名:国内网络作家排名

中国十大网络小说作家排名&#xff0c;在买购网的排名&#xff1a; 中国十大网络小说作家 网络小说作家排行榜 中国著名网络写手排名→MAIGOO生活榜 &#xff08;这个网站里还有很多其他的排名。&#xff09; 1&#xff0c;唐家三少 2&#xff0c;辰东 3&#xff0c;我吃西红…...

MySQL INSERT插入条件判断:如果不存在则插入

MySQL INSERT插入条件判断&#xff1a;如果不存在则插入&#xff08;转&#xff09; 我们经常需要进行sql的批量插入&#xff0c;要求&#xff1a;该条记录不存在则插入&#xff0c;存在则不插入。如果使用一条INSERT语句实现呢&#xff1f; ####普通的 INSERT INTO 插入&…...

CSM32RV003:国产高精度16位ADC低功耗RISC-V内核MCU

目录 高精度ADC工业应用工业数据采集应用CSM32RV003简介主要特性 高精度ADC工业应用 高精度ADC即高精度模数转换器&#xff0c;是一种能够将输入模拟信号转换为数字信号的芯片&#xff0c;在多种消费电子、工业、医疗和科研领域都有广泛应用。高精度ADC的主要特点是能够提供高…...

65道常问前端面试题总结react

面试题总结 一.Axios的实现原理 Axios 是一个基于 Promise 的 HTTP 客户端库&#xff0c;用于浏览器和 Node.js 环境。它可以发送 HTTP 请求并处理响应数据。下面是 Axios 实现的基本原理&#xff1a; 封装请求&#xff1a;Axios 提供了一个简单易用的 API&#xff0c;使得开…...

单片机学习1——点亮一个LED灯

Keil软件编写程序&#xff1a; 特殊功能寄存器声明&#xff1a; #include<reg52.h>sbit LED P1^0;void main() {LED 0;while(1); } 代码说明&#xff1a; sbit 语句是特殊功能位声明。 生成HEX文件&#xff0c;这个文件是下载到单片机里的文件。Options for Target…...

PyCharm 配置sqlite3驱动下载问题

单击View -> Tool Windows -> Database&#xff0c;打开Database窗体&#xff0c;之后进行配置&#xff0c;下载驱动包失败&#xff01; 解决 &#xff08;1&#xff09;下载Sqlite3驱动 下载地址: Central Repository: org/xerial/sqlite-jdbc 选择的版本是3.34.0,下载…...

NVMe-oF E-JBOF设计解析:WD RapidFlex网卡、OpenFlex Data24

OpenFlex Data24 NVMe-oF Storage Platform WD的SN840 NVMeSSD新品并没有太吸引我注意&#xff0c;因为它还是PCIe 3.0接口的&#xff0c;要知道Intel的PCIe 4.0 SSD都已经推出了。 但上面这个NVMe-oF&#xff08;NVMe over Fabric&#xff09;EBOF&#xff08;区别于普通JBO…...

X-AnyLabeling3.2实战:从零部署到自定义模型自动标注

1. X-AnyLabeling3.2安装与环境配置 第一次接触X-AnyLabeling这个开源标注工具时&#xff0c;我就被它的自动标注功能吸引了。相比传统的手动标注&#xff0c;它能节省80%以上的时间。不过安装过程确实有些坑要避开&#xff0c;这里分享我的实战经验。 首先需要准备Anaconda环境…...

3分钟搞定城通网盘限速:免费直连解析工具完整指南

3分钟搞定城通网盘限速&#xff1a;免费直连解析工具完整指南 【免费下载链接】ctfileGet 获取城通网盘一次性直连地址 项目地址: https://gitcode.com/gh_mirrors/ct/ctfileGet 你是否曾经因为城通网盘的限速下载而烦恼&#xff1f;面对几十KB/s的下载速度&#xff0c;…...

【pip】pip的各种操作

安装指定版本的库 pip install torchaudio2.1.2导出当前环境的python安装库 使用–local来去掉文件的安装路径 pip freeze --local > requirements.txt会导出当前环境的所有库&#xff0c;按需要删除 安装下载到本地的包 1.cd到包所在的文件夹 d: cd D:\迅雷下载2.pip insta…...

终极指南:PointNet激活函数性能大比拼 ReLU、LeakyReLU与Swish深度测试

终极指南&#xff1a;PointNet激活函数性能大比拼 ReLU、LeakyReLU与Swish深度测试 【免费下载链接】pointnet PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation 项目地址: https://gitcode.com/gh_mirrors/po/pointnet PointNet作为3D点…...

从“普惠”到“全能”:全志T153工业芯如何以HZ-T153_MiniEVM重塑工控开发体验

1. 为什么工业控制需要"普惠型"芯片&#xff1f; 在工业自动化领域&#xff0c;设备制造商常常面临一个两难选择&#xff1a;要么采用性能强大但价格昂贵的外国芯片方案&#xff0c;要么选择价格低廉但功能受限的入门级控制器。全志T153的出现打破了这种局面&#xf…...

YOLO12多尺度检测效果展示:同一图像不同分辨率输入结果对比图集

YOLO12多尺度检测效果展示&#xff1a;同一图像不同分辨率输入结果对比图集 1. 引言&#xff1a;为什么分辨率对目标检测如此重要&#xff1f; 想象一下&#xff0c;你用手机拍了一张远处的风景照&#xff0c;照片里有个很小的人影。当你把照片放大看时&#xff0c;这个人影可…...

AD20技巧:高效利用封装管理器批量更新原理图封装

1. 封装管理器基础操作指南 第一次接触AD20的封装管理器时&#xff0c;我也被它强大的批量处理能力惊艳到了。这个功能对于经常需要修改大量元器件封装的工程师来说简直是救命稻草。记得上周我接手一个老项目&#xff0c;发现原理图中80%的电阻封装都用了错误的0805尺寸&#x…...

计算机科学基础的重要性(操作系统、网络、组成原理)

计算机科学基础&#xff1a;数字世界的基石 在人工智能与云计算蓬勃发展的今天&#xff0c;计算机科学基础学科如操作系统、计算机网络和计算机组成原理&#xff0c;依然是技术创新的底层支柱。无论是开发高性能应用还是设计分布式系统&#xff0c;缺乏这些核心知识的程序员如…...

如何免费解锁Cursor AI Pro功能:3个核心技巧完整指南

如何免费解锁Cursor AI Pro功能&#xff1a;3个核心技巧完整指南 【免费下载链接】cursor-free-vip [Support 0.45]&#xff08;Multi Language 多语言&#xff09;自动注册 Cursor Ai &#xff0c;自动重置机器ID &#xff0c; 免费升级使用Pro 功能: Youve reached your tria…...

团队协作最小的良性开发闭环

问题陈述 现状&#xff1a;团队成员个人能力不差&#xff0c;但在「一起开发同一套系统」时&#xff0c;整体效率偏低、质量不稳&#xff1b;产品需求更新频繁、节奏快&#xff0c;且缺少前置规划与边界。 表层问题&#xff1a;产品、开发、测试对同一功能在「做什么、做到什么…...