Leetcode 两数之和 Ⅱ - 输入有序数组

在这里插入图片描述

这段代码实现了在一个非递减排序的数组中找到两个数,使它们的和等于目标值的算法。算法使用了双指针技术,具体思想如下:

算法思想:

  1. 初始化指针:定义两个指针 leftright,分别指向数组的起始位置和末尾位置。left 从左向右遍历,right 从右向左遍历。

  2. 计算当前和

    • 在循环中,每次计算 numbers[left]numbers[right] 的和,记为 sum
  3. 判断是否满足目标值

    • 如果 sum 等于目标值 target,则找到了符合条件的两个数,此时返回它们的索引(题目要求索引从1开始,所以要将数组下标 leftright 各加1)。
    • 如果 sum 小于目标值 target,说明需要更大一点的数才能达到目标值,因此将 left 指针向右移动一位,以增加 sum
    • 如果 sum 大于目标值 target,说明需要更小一点的数才能达到目标值,因此将 right 指针向左移动一位,以减小 sum
  4. 返回结果

    • 如果在循环结束后没有找到符合条件的两个数,返回一个空数组(虽然根据题目描述,总会有一个解,因此这一步通常不会被执行)。

时间复杂度

该算法的时间复杂度是 (O(n)),因为每次循环中指针 leftright 都会向中间移动,最多需要遍历整个数组一次。

总结

此算法利用了数组的有序性,通过双指针逐步逼近目标值,避免了暴力解法的多重循环,从而提升了效率。

java solution

class Solution {public int[] twoSum(int[] numbers, int target) {int left = 0;int right = numbers.length - 1;int sum = 0;int[] result = new int[2];while(left != right) {sum = numbers[left] + numbers[right];if(sum == target) {result[0] = left + 1;result[1] = right + 1;return result;}else if(sum < target) {left++;} else {right--;}}return new int[] {};     }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/9003.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

UE5.4 PCG 复制关卡实例

关卡实例&#xff1a;最大层级的管理&#xff0c;方便关卡级别的复制、重载 1.创建关卡实例&#xff0c;右箭生成PCG设置。注意&#xff1a;当关卡实例发生变化&#xff0c;需要重新手动再创建一次PCG设置 2.直接拖放到PCG图&#xff0c;设置如下 说明&#xff1a;PCG设置文…

C++ | Leetcode C++题解之第551题学生出勤记录I

题目&#xff1a; 题解&#xff1a; class Solution { public:bool checkRecord(string s) {int absents 0, lates 0;for (auto &ch : s) {if (ch A) {absents;if (absents > 2) {return false;}}if (ch L) {lates;if (lates > 3) {return false;}} else {lates…

Python 获取PDF的各种页面信息(页数、页面尺寸、旋转角度、页面方向等)

目录 安装所需库 Python获取PDF页数 Python获取PDF页面尺寸 Python获取PDF页面旋转角度 Python获取PDF页面方向 Python获取PDF页面标签 Python获取PDF页面边框信息 了解PDF页面信息对于有效处理、编辑和管理PDF文件至关重要。PDF文件通常包含多个页面&#xff0c;每个页…

设计模式(主要的五种)

1.设计模式&#xff1a; 设计模式就是代码设计经验 2.设计模式的类型&#xff1a; 分为三大类&#xff1a;创建型模式&#xff0c;结构型模式&#xff0c;行为模式 创建型模式&#xff1a; 单例模式&#xff1a;某个类只能有一个实例&#xff0c;提供一个全局的访问点。 工…

【北京迅为】itop-3588开发板摄像头使用手册Android12 双摄方案

本章节对应资料在网盘资料“iTOP-3588 开发板\02_【iTOP-RK3588 开发板】开发资料 \07_Android 系统开发配套资料\08_Android12 摄像头使用配套资料”目录下下载。 2.1 Android12 前摄后摄 网盘中默认的 Android12 源码支持四个摄像头单独打开&#xff0c;本小节我们来修改源码…

Javascript如何实现继承?

#一、是什么 继承&#xff08;inheritance&#xff09;是面向对象软件技术当中的一个概念。 如果一个类别B“继承自”另一个类别A&#xff0c;就把这个B称为“A的子类”&#xff0c;而把A称为“B的父类别”也可以称“A是B的超类” 继承的优点 继承可以使得子类具有父类别的…

测度论原创(三)

Morden Prob 文章目录 Morden ProbWeek3多维扩展和随机向量定理3.1推论&#xff1a;random variable的变换定理3.2 连续函数的可测性定理3.3 可测函数的线性组合关于拓展实数集的延伸定理3.4 可测函数的极限依旧为可测性随机变量的概率律&#xff08;Law of X X X&#xff09;…

Sql面试题二:请查询出用户连续三天登录的所有数据记录

问题&#xff1a; 现有用户登录记录表&#xff0c;请查询出用户连续三天登录的所有数据记录 id dt 1 2024-04-25 1 2024-04-26 1 2024-04-27 1 2024-04-28 1 2024-04-30 1 2024-05-01 1 2024-05-02 1 2024-05-04 1 2024-05-05 2 2…

vite中env uat/dev文件项目配置

1&#xff1a;图示 在vscode中显示的是&#xff08;在文件中显示不是文件夹而在vscode中显示是文件夹-- .env 而这个.env也是有内容的&#xff09; 2&#xff1a;.env文件内容 # 标题 VITE_APP_TITLE管理系统# 项目本地运行端口号 VITE_PORT80# open 运行 npm run dev 时自动打…

ssm基于JAVA的网上订餐管理系统+vue

系统包含&#xff1a;源码论文 所用技术&#xff1a;SpringBootVueSSMMybatisMysql 免费提供给大家参考或者学习&#xff0c;获取源码看文章最下面 需要定制看文章最下面 目 录 目 录 I 摘 要 III ABSTRACT IV 1 绪论 1 1.1 课题背景 1 1.2 研究现状 1 1.3 研究内容…

向日葵远程桌面Visual Studio白屏

问题描述 今天没带笔记本&#xff0c;想着拿 Ipad 远程写会代码&#xff0c;打开VS发现白屏了&#xff0c;看了看向日葵里面的设置有GPU加速&#xff0c;发现是和VS的GPU加速冲突了 解决方案&#xff08;远程同样可用&#xff09; ALT T 弹出工具菜单O 打开选项菜单A会取消…

Pandas | 数据分析时将特定列转换为数字类型 float64 或 int64的方法

类型转换 传统方法astype使用value_counts统计通过apply替换并使用astype转换 pd.to_numericx对连续变量进行转化⭐参数&#xff1a;返回值&#xff1a;示例代码&#xff1a; isnull不会检查空字符串 数据准备 有一组数据信息如下&#xff0c;其中主要将TotalCharges、MonthlyC…

Python+Appium编写脚本

一、环境配置 1、安装JDK&#xff0c;版本1.8以上 2、安装Python&#xff0c;版本3.x以上&#xff0c;用来解释python 3、安装node.js&#xff0c;版本^14.17.0 || ^16.13.0 || >18.0.0&#xff0c;用来安装Appimu Server 4、安装npm&#xff0c;版本>8&#xff0c;用…

WPF MVVM入门系列教程(三、数据绑定)

本文主要介绍WPF的数据绑定&#xff08;Data Binding&#xff09;功能&#xff0c;如果你已经熟悉本文的内容&#xff0c;可以跳过并直接阅读后面的文章。 什么是数据绑定 我们先来看一下MSDN上的说明&#xff1a; 数据绑定是在应用 UI 与其显示的数据之间建立连接的过程。 如…

关于Dell r730xd 老服务器的阵列卡 配置系统盘RAID 1

这里写自定义目录标题 关于Dell r730xd 老服务器的阵列卡 配置系统盘RAID 1操作步骤 关于Dell r730xd 老服务器的阵列卡 配置系统盘RAID 1 操作步骤 -开机后 按 Ctrl R 进入 RAID卡 配置界面&#xff0c;如下&#xff1a;-下面图片是 服务器中硬盘都已经准备好&#xff0c;并…

Qt Udp的组播(多播)、广播和单播

UDP通讯的基本概念和特点‌ UDP&#xff08;User Datagram Protocol&#xff0c;用户数据报协议&#xff09;是‌TCP/IP协议族中的一种无连接协议&#xff0c;主要用于那些对实时性要求较高而可靠性要求较低的应用场景。UDP的主要特点包括&#xff1a; ‌无连接‌&#xff1a;…

算法每日双题精讲——双指针(快乐数,盛最多水的容器)

&#x1f31f;快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。 &#x1f31f; 别再犹豫了&#xff01;快来订阅我们的算法每日双题精讲专栏&#xff0c;一起踏上算法学习的精彩之旅吧&#xff01;&#x1f4aa;…

C语言 | Leetcode C语言题解之第551题学生出勤记录I

题目&#xff1a; 题解&#xff1a; bool checkRecord(char* s) {int absents 0, lates 0;int n strlen(s);for (int i 0; i < n; i) {char c s[i];if (c A) {absents;if (absents > 2) {return false;}}if (c L) {lates;if (lates > 3) {return false;}} els…

【未解决】vite反向代理问题

文章目录 可行网页直接访问&#xff0c;数据正常返回不使用反向代理&#xff0c;直接用axios可以得到数据postman测试也正常 不行-vite反向代理出问题case1命令行测试 可行 网页直接访问&#xff0c;数据正常返回 在地址栏输入 https://api.binance.com/api/v3/ticker/price?…

github使用基础

要通过终端绑定GitHub账号并进行文件传输&#xff0c;你需要使用Git和SSH密钥来实现安全连接和操作。以下是一个基本流程&#xff1a; 设置GitHub和SSH 检查Git安装 通过终端输入以下命令查看是否安装Git&#xff1a; bash 复制代码 git --version配置Git用户名和邮箱 bash …