【算法学习】两数之和II - 输入有序数组
题目描述
原题链接
给你一个下标从 1 开始的整数数组 numbers
,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target
的两个数。如果设这两个数分别是 numbers[index1]
和 numbers[index2]
,则 1 <= index1 < index2 <= numbers.length
。
以长度为 2 的整数数组 [index1, index2]
的形式返回这两个整数的下标 index1
和 index2
。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1:
输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2:
输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3:
输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示:
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers
按 非递减顺序 排列-1000 <= target <= 1000
- 仅存在一个有效答案
双指针法
思路分析
我们观察题目可以发现,数组是已经排好序的,那么我们可以直接定义两个元素来分别指向 数组头
和 数组尾
,然后循环使两个指针移动,直到最终算出我们需要的结果。
假设左指针为start,右指针为end,并将左右指针所对应的元素的和设为sum,那么我们就可以发现:
- 当 sum==target 时,就可以得到我们需要的结果
- 当 sum>target 时,我们需要将右指针对应的元素变小一些,那么就需要 将右指针向左移动一个元素,也就是
end--
- 当 sum<target 时,我们需要将左指针对应的元素变大一些,那么就需要 将左指针向右移动一个元素,也就是
start++
我们可以通过下图来理解这个规律。
图解
代码实现
public int[] twoSum(int[] numbers, int target) {if (null == numbers) {return new int[0];}int start = 0;int end = numbers.length - 1;while (start < end) {int sum = numbers[start] + numbers[end];if (sum == target) {return new int[]{start + 1, end + 1};} else if (sum > target) {end--;} else {start++;}}return new int[0];
}
二分查找法
思路分析
那么我们将题目带入,假设左指针为 start,右指针为 end,并将左右指针中间的下标为 middle,即可得到:
- 当 numbers[middle]==target 时,我们即可得到需要的结果
- 当 numbers[middle]>target 时,说明 中间数大于预期结果,结果在左半部分,那么我们需要 将右指针移动至middle的位置,并重新取middle的位置。
- 当 numbers[middle]<target 时,说明 中间数小于预期结果,结果在右半部分,那么我们需要 将左指针移动至middle的位置,并重新取middle的位置。
我们通过下图来理解。
图解
代码实现
public int[] twoSum(int[] numbers, int target) {if (null == numbers) {return new int[0];}for (int i = 0; i < numbers.length; ++i) {int start = i + 1;int end = numbers.length - 1;while (start <= end) {int middle = (end - start) / 2 + start;if (numbers[middle] == target - numbers[i]) {return new int[]{i + 1, middle + 1};} else if (numbers[middle] > target - numbers[i]) {end = middle - 1;} else {start = middle + 1;}}}return new int[0];}
总结
我们使用了两种写法来完成这个题目:双指针法
和 二分查找法
。
其中在 双指针法
中,数组最多遍历n次,则时间复杂度为 O(n) ,空间复杂度为O(1) 。
在 二分查找法
中,遍历数组的时间复杂度为 O(n) ,二分查找来寻找参数的时间复杂度为 O ( l o g n ) O(log_n) O(logn) ,所以在该题目中,总时间复杂度为 O ( n l o g n ) O(nlog_n) O(nlogn) ,空间复杂度为O(1) 。
推荐
关注博客和公众号获取最新文章
Bummon’s Blog | Bummon’s Home | 公众号
相关文章:
【算法学习】两数之和II - 输入有序数组
题目描述 原题链接 给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 < index1 < …...
聚观早报|京东称在技术投入没有止境;木蚁机器人完成B2轮融资
【聚观365】8月18日消息 京东零售CEO表示在技术上投入没有止境 木蚁机器人完成B2轮超亿元融资 耐能推出AI芯片KL730 三星电子泰勒晶圆厂首家客户是AI半导体厂商 韩国新能源汽车7月出口额同比大增36% 京东零售CEO表示在技术上投入没有止境 近日,京东零售CEO辛利…...
C语言:选择+编程(每日一练)
目录 选择题: 题一: 题二: 题三: 题四: 题五: 编程题: 题一:尼科彻斯定理 示例1 题二:等差数列 示例2 本人实力有限可能对一些地方解释和理解的不够清晰&…...
信道数据传输速率、码元传输速率、调制速度,信号传播速度之间的关系
1、信道数据传输速率(bit/s) 举例:移动通信中的数据传输速率。假设你的手机连接到4G网络,该网络的最大理论数据传输速率为100 Mbps。这意味着在理想情况下,你的手机可以以每秒100兆比特的速度传输数据。 2、码元传输速…...
docker的使用方法总结
Docker是一个非常强大的工具,它可以用于创建、部署和运行应用程序。以下是一些docker相关的常用指令, 1、查看docker版本 docker version 2、查看正在运行的Docker容器 docker ps 3、查看所有的docker容器(包括没有运行的容器࿰…...
【C#】条码管理操作手册
前言:本文档为条码管理系统操作指南,介绍功能使用、参数配置、资源链接,以及异常的解决等。思维导图如下: 一、思维导图 二、功能操作–条码打印(客户端) 2.1 参数设置 功能介绍:二维码图片样…...
RabbitMq-发布确认高级(避坑指南版)
在初学rabbitMq的时候,伙伴们肯定已经接触到了“发布确认”的概念,但是到了后期学习中,会接触到“springboot”中使用“发布确认”高级的概念。后者主要是解决什么问题呢?或者是什么样的场景引出这样的概念呢? 在生产环…...
Blender增强现实3D模型制作指南【AR】
推荐:用 NSDT编辑器 快速搭建可编程3D场景 将静态和动画 3D 内容集成到移动增强现实 (AR) 体验中是增强用户沉浸感和参与度的高效方法。 然而,为 AR 创建 3D 对象可能相当艰巨,尤其是对于那些缺乏 3D 建模经验的人来说。 与添加视频或照片 AR…...
Java查看https证书过期时间(JKS,CERT)
在这里需要使用X.509 证书的抽象类 X509Certificate 。此类提供了一种访问 X.509 证书所有属性的标准方式。 这些证书被广泛使用以支持 Internet 安全系统中的身份验证和其他功能。常见的应用包括增强保密邮件 (PEM)、传输层安全 (SSL)、用于受信任软件发布的代码签名和安全电…...
关于vue,记录一次修饰符.stop和.once的使用,以及猜想。
内置指令 | Vue.js 在vue的api里,关于v-on有stop和once两个事件标签。 .stop - 调用 event.stopPropagation()。.once - 最多触发一次处理函数。 原有主要代码和页面效果 (无stop和once): ...<div class"div" click"di…...
解决git reset --soft HEAD^撤销commit时报错
今天在使用git回退功能的时候,遇到以下错误: 解决git reset --soft HEAD^撤销commit时报错 问题: 在进行完commit后,想要撤销该commit,于是使用了git reset --soft HEAD^命令,但是出现如下报错࿱…...
【BASH】回顾与知识点梳理(三十四)
【BASH】回顾与知识点梳理 三十四 三十四. 认识系统服务(二)34.1 systemctl 针对 service 类型的配置文件systemctl 配置文件相关目录简介systemctl 配置文件的设定项目简介[Unit] 部份[Service] 部份[Install] 部份 两个 vsftpd 运作的实例多重的重复设…...
Python可视化在量化交易中的应用(11)_Seaborn折线图
举个栗子,用seaborn绘制折线图。 Seaborn中折线图的绘制方法 在seaborn中,我们一般使用sns作为seaborn模块的别名,因此,在下文中,均以sns指代seaborn模块。 seaborn中绘制折线图使用的是sns.plot()函数: …...
无涯教程-TensorFlow - TensorBoard可视化
TensorFlow包含一个可视化工具,称为TensorBoard,它用于分析数据流图,还用于了解机器学习模型。 TensorBoard的重要功能包括查看有关垂直对齐的任何图形的参数和详细信息的不同类型统计的视图。 深度神经网络包括多达36,000个节点…...
[uni-app] uview封装Popup组件,处理props及v-model的传值问题
文章目录 需求及效果遇到的问题解决的办法偷懒的写法 需求及效果 uView(1.x版本)中, 有Pop弹出层的组件, 现在有个需求是,进行简单封装,有些通用的设置不想每次都写(比如 :mask-custom-style"{background: rgba(0, 0, 0, 0.7)}"这种) 然后内部内容交给插槽去自己随…...
【C++】int a;和int *p=new int;有什么区别?
2023年8月19日,周六早上 int a; 和 int *p new int; 之间有以下区别: 1. 内存分配方式:int a; 是在栈上分配内存,而 int *p new int; 是在堆上动态分配内存。 2. 生命周期:int a; 的生命周期与其所在的作用域相同&…...
redis事务管理
目录 一、redis事务定义 二、事务控制命令——Multi、Exec、discard 三、事务的错误处理 四、事务的冲突问题 悲观锁 乐观锁 WATCH unwatch 五、事务特性 单独的隔离操作 没有隔离级别的概念 不保证原子性 一、redis事务定义 Redis 事务是一个单独的隔离操作&…...
TPS_C++版本及功能支持备注
TPS_C版本及功能支持备注 相关参考链接C23:https://zh.cppreference.com/w/cpp/23 相关参考链接C20:https://zh.cppreference.com/w/cpp/20 相关参考链接C17:https://zh.cppreference.com/w/cpp/17 相关参考链接C14:https://zh.cp…...
同步jenkinsfile流水线(sync-job)
环境 变量:env(环境变量:sit/dev/simulation/prod/all),job(job-name/all)目录:/var/lib/jenkins/jenkinsfile environment.json: [roottest-01 jenkinsfile]# cat env…...
STM32单片机WIFI-APP智能温室大棚系统CO2土壤湿度空气温湿度补光
实践制作DIY- GC0161--智能温室大棚系统 基于STM32单片机设计---智能温室大棚系统 二、功能介绍: 电路组成:STM32F103CXT6最小系统LCD1602显示器DHT11空气温度湿度光敏电阻光强土壤湿度传感器SGP30二氧化碳传感器 1个继电器(空气加湿&#x…...
SpringBoot复习:(52)不再需要使用@EnableTransactionManagement的原因
在Spring项目中,要用事务,需要EnableTransactionManagement注解加Transactional注解。而在SpringBoot项目,有事务的自动配置类TransactionAutoConfiguration,代码如下: 可以在其内部类EnableTransactionManagementConfiguratio…...
HackNos 3靶场
配置 进入控制面板配置网卡 第一步:启动靶机时按下 shift 键, 进入以下界面 第二步:选择第二个选项,然后按下 e 键,进入编辑界面 将这里的ro修改为rw single init/bin/bash,然后按ctrlx,进入…...
【办公自动化】使用Python批量生成PPT版荣誉证书
🤵♂️ 个人主页:艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞Ǵ…...
【C++深入浅出】初识C++中篇(引用、内联函数)
目录 一. 前言 二. 引用 2.1 引用的概念 2.2 引用的使用 2.3 引用的特性 2.4 常引用 2.5 引用的使用场景 2.6 传值、传引用效率比较 2.7 引用和指针的区别 三. 内联函数 3.1 内联函数的概念 3.2 内联函数的特性 一. 前言 上期说道,C是在C的基础之上&…...
前端:VUE2中的父子传值
文章目录 一、背景什么是父子传值二、业务场景子传父1、在父页面中引入子页面2、子传父:父组件标识3、子传父:子组件标识 父传子父组件调用子组件中的方法 总结: 一、背景 最近做项目中需要使用到流工作,在这里流工作需要用到父子…...
【100天精通python】Day40:GUI界面编程_PyQt 从入门到实战(完)_网络编程与打包发布
目录 8 网络编程 8.1 使用PyQt 网络模块进行网络通信 服务器端示例 客户端示例 8.2 处理网络请求和响应 9 打包和发布 9.1 创建可执行文件或安装程序 9.2 解决依赖问题 9.3 发布 PyQt 应用到不同平台 9.3.1 发布到 Windows 9.3.2 发布到 macOS 9.3.3 发布到 Linux 9…...
Redis——set类型详解
概要 Set(集合),将一些有关联的数据放到一起,集合中的元素是无序的,并且集合中的元素是不能重复的 之前介绍的list就是有序的,对于列表来说[1, 2, 3] 和 [2, 1, 3]是两个不同的列表,而对于集合…...
redis---》高级用法之慢查询/pipline与事务/发布订阅/bitmap位图/HyperLogLog/GEO地理位置信息/持久化
高级用法之慢查询 # 配置一个时间,如果查询时间超过了我们设置的时间,我们就认为这是一个慢查询 # 配置的慢查询,只在命令执行阶段# 慢查询演示-设置慢查询---》只要超过某个时间的命令---》都会保存起来# 设置记录所有命令CONFIG SET slowl…...
Find My资讯|苹果Vision Pro开发者需将设备配对 AirTag
最近苹果Vision Pro获开发者申请,苹果要求获批的申请者使用 Measure and Fit 应用确认合适的佩戴尺寸,并会根据申请者提交的信息,定制不同的 Vision Pro 开发者套件,以便于契合申请者的面部特征,提供更好的佩戴体验。 …...
Go 语言中排序的 3 种方法
原文链接: Go 语言中排序的 3 种方法 在写代码过程中,排序是经常会遇到的需求,本文会介绍三种常用的方法。 废话不多说,下面正文开始。 使用标准库 根据场景直接使用标准库中的方法,比如: sort.Intsso…...
12----Emoji表情
本节我们主要讲解markdown的Emoji 在 Markdown 里使用 Emoji 表情有两种方法:一种是直接输入 Emoji 表情,另一种是使用 Emoji 表情短码(emoji shartcodes)。 一、打印方式: 直接输入 Emoji 表情:在 Markdown 中,可以直接输入 Em…...
C++四种强制类型转换
一、C强制转换与C强制转换 c语言强制类型转换主要用于基础的数据类型间的转换,语法为: (type-id)expression//转换格式1 type-id(expression)//转换格式2c除了能使用c语言的强制类型转换外,还新增了四种强制类型转换:static_cas…...
git仓库新建上传记录
新建git仓会出现版本分支问题,解决过程: 其他的前期绑定之类的传送:https://blog.csdn.net/qq_37194189/article/details/130767397 大概思路:新建一个分支,上传,合并,删除分支 git branch …...
flutter调用so
lutter是一种基于Dart语言的跨平台开发框架,通常用于开发Android和iOS应用程序。如果您想要在Flutter应用程序中调用一个SO库,您可以按照以下步骤进行操作: 首先,将您的SO库文件复制到Flutter项目的“lib”目录下。 接下来&…...
c#依赖注入
依赖注入(Dependency Injection,简称 DI)是一种设计模式,用于将对象的创建和管理责任从使用它的类中分离出来,从而实现松耦合和易于测试的代码。在 C# 中,依赖注入通常通过以下方式实现: 构造函数注入(Constructor Injection): 这是最常见的依赖注入方式,通过类的构…...
Django框架使用定时器-APScheduler实现定时任务:django实现简单的定时任务
一、系统环境依赖 系统:windows10 python: python3.9.0 djnago3.2.0 APScheduler3.10.1 二、django项目配置 1、创建utils包,在包里面创建schedulers包 utils/schedulers/task.py #1、设置 Django 环境,就可以导入项目的模型类这些了 …...
Go学习笔记之数据类型
文章目录 GO数据类型数组array切片slice集合map结构体make和new GO数据类型 在go语言中,定义的全局数据结构不使用不会报错,定义的局部数据结构必须使用,否则报错;建议定义的数据类型就要使用,要么不定义。 数组array …...
Spring Cloud 微服务
前言 Spring Cloud 中的所有子项目都依赖Spring Boot框架,所以Spring Boot 框架的版本号和Spring CLoud的版本号之间也存在以来及兼容关系。 Spring Cloud生态下的服务治理的解决方案主要有两个: Spring Cloud Netfix 和 Spring Cloud Alibaba。这两个…...
SpringBoot属性配置
SpringBoot提供了多种属性配置方式 application.properties server.port80 application.yml server:port: 81application.yaml server:port: 82SpringBoot配置文件加载顺序 application.properties > application.yml > application.yaml常用配置文件种类 application.…...
算法通关村第十关 | 归并排序
1. 归并排序原理 归并排序(MERARE-SORT)简单来说就是将大的序列先视为若干个比较小的数组,分成比较小的结构,然后是利用归并的思想实现的排序方法,该算法采用经典的分治策略(分就是将问题分成一些小的问题分…...
SpringBoot3集成Kafka
标签:Kafka3.Kafka-eagle3; 一、简介 Kafka是一个开源的分布式事件流平台,常被用于高性能数据管道、流分析、数据集成和关键任务应用,基于Zookeeper协调的处理平台,也是一种消息系统,具有更好的吞吐量、内…...
css学习1
1、样式定义如何显示元素。 2、样式通常保存至外部的css文件中。 3、样式可以使内容与表现分离。 4、css主要有两部分组成:选择器与一条或多条声明。 选择器通常为要改变的html元素,每条声明由一个属性和一个值组成。每个属性有一个值,属性…...
rust踩雷笔记(1)——切片传参和解引用赋值
最近学习rust,网上资料还是很有限,做题遇到的问题,有时需要自己试验。把自己做题过程遇到的问题,和试验的结论,做一些简单记录。 阅读下列文字和代码 用切片(的引用)做参数要非常小心ÿ…...
安全 1自测
常见对称加密算法: DES(Data Encryption Standard):数据加密标准,速度较快,适用于加密大量数据的场合; 3DES(Triple DES):是基于DES,对一块数据用…...
寻路算法小游戏
寻路算法小demo 寻路算法有两种,一种是dfs 深度优先算法,一种是 dfs 深度优先算法 深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义,深度优先,则是以深度为准则,先一条路走到底,直到达到目标。这…...
CSS基础 知识点总结
一.CSS简介 1.1 CSS简介 ① CSS指的是层叠样式表,用来控制网页外观的一门技术 ② CSS发展至今,经历过CSS1.0 CSS2.0 CSS2.1 CSS3.0这几个版本,CSS3.0是CSS最新版本 1.2 CSS引入方式 ① 在一个页面引入CSS,共有三种方式 外部…...
自动执行探索性数据分析 (EDA),更快、更轻松地理解数据
一、说明 EDA是 exploratory data analysis (探索性数据分析 )的缩写。所谓EDA就是在数据分析之前需要对数据进行以此系统性研判,在这个研判后,得到基本的数据先验知识,在这个基础上进行数据分析。本文将在R语言和python语言的探索性处理。 摄…...
【自定义系统服务】【android13】添加自定义java系统服务
背景 在平时的业务开发中,我们往往需要开发自定义的系统服务来处理自己特殊的需求,这里介绍的是添加自定义的Java系统服务,可以在系统App中直接调用 定义aidl Binder默认可以传输基本类型的数据,如果要传递类对象,则这个类需要实现序列化。我们先定义一个序列化的自定义…...
【Sklearn】基于随机梯度下降算法的数据分类预测(Excel可直接替换数据)
【Sklearn】基于随机梯度下降算法的数据分类预测(Excel可直接替换数据) 1.模型原理2.模型参数3.文件结构4.Excel数据5.下载地址6.完整代码7.运行结果1.模型原理 随机梯度下降(Stochastic Gradient Descent,SGD)是一种优化算法,用于训练模型的参数以最小化损失函数。在分…...
44、TCP报文(二)
接上节内容,本节我们继续TCP报文首部字段含义的学习。上节为止我们学习到“数据偏移”和“保留”字段。接下来我们学习后面的一些字段(暂不包含“检验和”的计算方法和选项字段)。 TCP首部结构(续) “数据偏移”和“保…...