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

【算法学习】两数之和II - 输入有序数组

题目描述

原题链接

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1]numbers[index2] ,则 1 <= index1 < index2 <= numbers.length

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1index2

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1:

输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释: 27 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2]

示例 2:

输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:24 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3]

示例 3:

输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-10 之和等于目标数 -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++

我们可以通过下图来理解这个规律。

图解

双指针法.gif

代码实现

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的位置。

我们通过下图来理解。

图解

1692181098346.gif

代码实现

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 &#xff0c;该数组已按 非递减顺序排列 &#xff0c;请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] &#xff0c;则 1 < index1 < …...

聚观早报|京东称在技术投入没有止境;木蚁机器人完成B2轮融资

【聚观365】8月18日消息 京东零售CEO表示在技术上投入没有止境 木蚁机器人完成B2轮超亿元融资 耐能推出AI芯片KL730 三星电子泰勒晶圆厂首家客户是AI半导体厂商 韩国新能源汽车7月出口额同比大增36% 京东零售CEO表示在技术上投入没有止境 近日&#xff0c;京东零售CEO辛利…...

C语言:选择+编程(每日一练)

目录 选择题&#xff1a; 题一&#xff1a; 题二&#xff1a; 题三&#xff1a; 题四&#xff1a; 题五&#xff1a; 编程题&#xff1a; 题一&#xff1a;尼科彻斯定理 示例1 题二&#xff1a;等差数列 示例2 本人实力有限可能对一些地方解释和理解的不够清晰&…...

信道数据传输速率、码元传输速率、调制速度,信号传播速度之间的关系

1、信道数据传输速率&#xff08;bit/s&#xff09; 举例&#xff1a;移动通信中的数据传输速率。假设你的手机连接到4G网络&#xff0c;该网络的最大理论数据传输速率为100 Mbps。这意味着在理想情况下&#xff0c;你的手机可以以每秒100兆比特的速度传输数据。 2、码元传输速…...

docker的使用方法总结

Docker是一个非常强大的工具&#xff0c;它可以用于创建、部署和运行应用程序。以下是一些docker相关的常用指令&#xff0c; 1、查看docker版本 docker version 2、查看正在运行的Docker容器 docker ps 3、查看所有的docker容器&#xff08;包括没有运行的容器&#xff0…...

【C#】条码管理操作手册

前言&#xff1a;本文档为条码管理系统操作指南&#xff0c;介绍功能使用、参数配置、资源链接&#xff0c;以及异常的解决等。思维导图如下&#xff1a; 一、思维导图 二、功能操作–条码打印&#xff08;客户端&#xff09; 2.1 参数设置 功能介绍&#xff1a;二维码图片样…...

RabbitMq-发布确认高级(避坑指南版)

在初学rabbitMq的时候&#xff0c;伙伴们肯定已经接触到了“发布确认”的概念&#xff0c;但是到了后期学习中&#xff0c;会接触到“springboot”中使用“发布确认”高级的概念。后者主要是解决什么问题呢&#xff1f;或者是什么样的场景引出这样的概念呢&#xff1f; 在生产环…...

Blender增强现实3D模型制作指南【AR】

推荐&#xff1a;用 NSDT编辑器 快速搭建可编程3D场景 将静态和动画 3D 内容集成到移动增强现实 (AR) 体验中是增强用户沉浸感和参与度的高效方法。 然而&#xff0c;为 AR 创建 3D 对象可能相当艰巨&#xff0c;尤其是对于那些缺乏 3D 建模经验的人来说。 与添加视频或照片 AR…...

Java查看https证书过期时间(JKS,CERT)

在这里需要使用X.509 证书的抽象类 X509Certificate 。此类提供了一种访问 X.509 证书所有属性的标准方式。 这些证书被广泛使用以支持 Internet 安全系统中的身份验证和其他功能。常见的应用包括增强保密邮件 (PEM)、传输层安全 (SSL)、用于受信任软件发布的代码签名和安全电…...

关于vue,记录一次修饰符.stop和.once的使用,以及猜想。

内置指令 | Vue.js 在vue的api里&#xff0c;关于v-on有stop和once两个事件标签。 .stop - 调用 event.stopPropagation()。.once - 最多触发一次处理函数。 原有主要代码和页面效果 &#xff08;无stop和once&#xff09;: ...<div class"div" click"di…...

解决git reset --soft HEAD^撤销commit时报错

今天在使用git回退功能的时候&#xff0c;遇到以下错误&#xff1a; 解决git reset --soft HEAD^撤销commit时报错 问题&#xff1a; 在进行完commit后&#xff0c;想要撤销该commit&#xff0c;于是使用了git reset --soft HEAD^命令&#xff0c;但是出现如下报错&#xff1…...

【BASH】回顾与知识点梳理(三十四)

【BASH】回顾与知识点梳理 三十四 三十四. 认识系统服务&#xff08;二&#xff09;34.1 systemctl 针对 service 类型的配置文件systemctl 配置文件相关目录简介systemctl 配置文件的设定项目简介[Unit] 部份[Service] 部份[Install] 部份 两个 vsftpd 运作的实例多重的重复设…...

Python可视化在量化交易中的应用(11)_Seaborn折线图

举个栗子&#xff0c;用seaborn绘制折线图。 Seaborn中折线图的绘制方法 在seaborn中&#xff0c;我们一般使用sns作为seaborn模块的别名&#xff0c;因此&#xff0c;在下文中&#xff0c;均以sns指代seaborn模块。 seaborn中绘制折线图使用的是sns.plot()函数&#xff1a; …...

无涯教程-TensorFlow - TensorBoard可视化

TensorFlow包含一个可视化工具&#xff0c;称为TensorBoard&#xff0c;它用于分析数据流图&#xff0c;还用于了解机器学习模型。 TensorBoard的重要功能包括查看有关垂直对齐的任何图形的参数和详细信息的不同类型统计的视图。 深度神经网络包括多达36&#xff0c;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日&#xff0c;周六早上 int a; 和 int *p new int; 之间有以下区别&#xff1a; 1. 内存分配方式&#xff1a;int a; 是在栈上分配内存&#xff0c;而 int *p new int; 是在堆上动态分配内存。 2. 生命周期&#xff1a;int a; 的生命周期与其所在的作用域相同&…...

redis事务管理

目录 一、redis事务定义 二、事务控制命令——Multi、Exec、discard 三、事务的错误处理 四、事务的冲突问题 悲观锁 乐观锁 WATCH unwatch 五、事务特性 单独的隔离操作 没有隔离级别的概念 不保证原子性 一、redis事务定义 Redis 事务是一个单独的隔离操作&…...

TPS_C++版本及功能支持备注

TPS_C版本及功能支持备注 相关参考链接C23&#xff1a;https://zh.cppreference.com/w/cpp/23 相关参考链接C20&#xff1a;https://zh.cppreference.com/w/cpp/20 相关参考链接C17&#xff1a;https://zh.cppreference.com/w/cpp/17 相关参考链接C14&#xff1a;https://zh.cp…...

同步jenkinsfile流水线(sync-job)

环境 变量&#xff1a;env&#xff08;环境变量&#xff1a;sit/dev/simulation/prod/all&#xff09;&#xff0c;job&#xff08;job-name/all&#xff09;目录&#xff1a;/var/lib/jenkins/jenkinsfile environment.json&#xff1a; [roottest-01 jenkinsfile]# cat env…...

STM32单片机WIFI-APP智能温室大棚系统CO2土壤湿度空气温湿度补光

实践制作DIY- GC0161--智能温室大棚系统 基于STM32单片机设计---智能温室大棚系统 二、功能介绍&#xff1a; 电路组成&#xff1a;STM32F103CXT6最小系统LCD1602显示器DHT11空气温度湿度光敏电阻光强土壤湿度传感器SGP30二氧化碳传感器 1个继电器&#xff08;空气加湿&#x…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...