剑指 Offer 57. 和为s的两个数字
一、题目
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]
示例 2:
输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]
限制:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
二、题目分析&解题思路
2.1 从头往后遍历法
有没有人和我一样,想着从头往后遍历,例如 第一个用例
2,7,11,15
依次把每个数字 与 target - nums[i] 存到 map 里
存成这样:
2,7
7,2
…
例如先 存 2,7
再遍历 7 时 计算 target - 7 = 2 ,再去用 map.find(2); 找到了即可
否则继续往后遍历
代码实现:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {map<int, int> mapTemp;for(int i = 0; i < nums.size(); i++){if(nums[i] > target){break;}int iTemp = target - nums[i];if(mapTemp.find(iTemp) == mapTemp.end()){mapTemp.insert(make_pair(nums[i], iTemp));}else{nums.resize(0);auto iter = mapTemp.find(iTemp);nums.push_back(iter->first);nums.push_back(iter->second);break;}}return nums;}
};

虽然过了但是可以看到,所耗时间和所额外开辟的空间都非常大,这代码还不如不写
时间复杂度:常规遍历 O(N) 加上每一次的 map.find nLog(n) ,还额外开辟了map 存储 2N的空间,太鸡肋了,完全忽略了 升序这一个特点;
因此可以考虑使用双指针法
2.2 双指针遍历法
以示例 1 的用例来看,数组是升序,左小右大,那么只需要做如下操作:

代码实现:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int left = 0;int right = nums.size() -1;while(left < right){if((nums[left] + nums[right]) > target){//说明右边的数字太大了right--;}else if((nums[left] + nums[right]) < target){//说明左边的数字太小了left++;}else{nums[0] = nums[left];nums[1] = nums[right];nums.resize(2);break;}}return nums;}
};

是不是立马好了一点,但是感觉还是很慢,还有没有优化的空间呢?
2.3 缩减范围+双指针法
我们继续来看 这一组用例
2 7 11 15
target = 9;
用双指针的话,其实 11 15 这两个数字完全没有必要去遍历,因为 其 已经 大于 target 了。且题目已经告知

说明没有负数,那么说明这一部分可以舍去,可以做一个裁剪,把范围缩小,把多余的右部分数组元素舍去,减少 双指针法的 right 区间,降低时间复杂度。
int GetRightIndex(vector<int>& nums, int target){int left = 0;int right = nums.size()-1;while(left < right){int mid = (left + right) /2;if(nums[mid] < target){left = mid + 1;}if(nums[mid] >= target){right = mid;}}return right;}
可以看到速度有效提升

三、代码实现
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int left = 0;int right = GetRightIndex(nums, target);while(left < right){if((nums[left] + nums[right]) > target){//说明右的数字太大了right--;}else if((nums[left] + nums[right]) < target){//左边的数字太小了left++;}else{nums[0] = nums[left];nums[1] = nums[right];nums.resize(2);break;}}return nums;}int GetRightIndex(vector<int>& nums, int target){int left = 0;int right = nums.size()-1;int mid = 0;while(left < right){mid = (left + right) /2;if(nums[mid] < target){left = mid + 1;}if(nums[mid] >= target){right = mid;}}return right;}
};

相关文章:
剑指 Offer 57. 和为s的两个数字
一、题目 输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。 示例 1: 输入:nums [2,7,11,15], target 9 输出:[2,7] 或者 [7…...
PDF转word在线转换方法!操作简单又高效
相信很多已经工作的人都知道,PDF文件格式的优点在于兼容性强、安全性高,而且查看和传输给他人都很方便。但是,这种格式的文件也有不太方便的地方,那就是不能对文件内容进行编辑和修改。对于许多人来说,如果想要编辑修改…...
Jquery项目中使用vue.js
大家在工作的情况中,可能会遇到之前的老项目采用jq书写,或者修改或者新增功能在jq中,原始jq的项目,代码可维护性很差,一个页面几千行jq,可维护性很差,工作量巨大,所以这个时候大家可以引入vue.js。 第一步:引入vue.js…...
蓝桥杯 删除字符
题目描述 给定一个单词,请问在单词中删除 t 个字母后,能得到的字典序最小的单词是什么? 输入描述 输入的第一行包含一个单词,由大写英文字母组成。 第二行包含一个正整数 t。 其中,单词长度不超过 100,…...
析构函数 对象数组 对象指针
🐶博主主页:ᰔᩚ. 一怀明月ꦿ ❤️🔥专栏系列:线性代数,C初学者入门训练,题解C,C的使用文章 🔥座右铭:“不要等到什么都没有了,才下定决心去做” …...
Vue对Axios网络请求进行封装
一、为什么要对网络请求进行封装? 因为网络请求的使用率实在是太高了,我们有的时候为了程序的一个可维护性,会把同样的东西放在一起,后期找起来会很方便,这就是封装的主要意义。 二、如何进行封装? 1、将…...
Android framework HAL(HIDL)
简述 当你在Android系统中使用不同的硬件设备(例如摄像头、传感器、音频设备等)时,你需要与硬件抽象层(HAL)进行通信。 HAL是一个中间层,它充当了硬件和应用程序之间的桥梁。但是,由于硬件设备…...
QML 模型(ListModel)
LIstModel(列表模型) ListModel 是ListElement定义的简单容器,每个定义都包含数据角色。内容可以在 QML 中动态定义或显式定义。 属性: count模型中数据条目的数量dynamic动态角色,默认情况下,角色的类型…...
你还在调戏AI,有的公司已经用ChatGPT开展业务了
近日,OpenAI 正式宣布开放 ChatGPT 和 Whisper 两个模型的 API,API 版本的ChatGPT 不仅功能更多、性能更强,而且还更便宜一一相当于目前 GPT-3 模型价格打一折!划重点OpenAl正式开放 ChatGPT 和 Whisper 模型的 API,目前 SnapChat…...
DatenLord前沿技术分享 No.20
达坦科技专注于打造新一代开源跨云存储平台DatenLord,致力于解决多云架构、多数据中心场景下异构存储、数据统一管理需求等问题,以满足不同行业客户对海量数据跨云、跨数据中心高性能访问的需求。喷泉码具有极高的纠错能力,且具有低延迟、地复…...
基于vivado(语言Verilog)的FPGA学习(1)——了解viviado面板和编译过程
基于vivado(语言Verilog)的FPGA学习(1)——了解程序面板和编译过程 每日废话:最近找实习略微一些焦虑,不想找软件开发,虽然有些C和python基础(之前上课学的),…...
PACS(CT、CR、DR、MR、DSA、RF医院影像管理系统源码)
PACS具体功能介绍: 病人、采集、观片、三维、报告、照相、退出、文件、图像采集、观片操作、三维、测量标注、诊断报告、照相打印、统计报表、系统管理、帮助、病人浏览器、选择数据源、打开图像、病人登记、工作列表、采集、打开画廊。 DICOM查询/获取:…...
Centos7 安装Mysql8.0
1、到指定目录下下载安装包[rootVM-0-14-centos ~]# cd /usr/local/src2、下载mysql8[rootVM-0-14-centos src]# wget https://dev.mysql.com/get/Downloads/MySQL-8.0/mysql-8.0.20-linux-glibc2.12-x86_64.tar.xz3、解压mysql8, 通过xz命令解压出tar包, 然后通过t…...
2023年全国最新道路运输从业人员精选真题及答案18
百分百题库提供道路运输安全员考试试题、道路运输从业人员考试预测题、道路安全员考试真题、道路运输从业人员证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 181.某客运企业拥有55辆营运客车,下列关于该企业设置…...
web worker的基本使用案例
文件目录如下 代码按照顺序分别如下 webworker.html <!DOCTYPE html> <html lang"en"><head><meta charset"utf-8" /><meta http-equiv"X-UA-Compatible" content"IEedge" /><meta name"viewpo…...
机器看世界
博主简介 博主是一名大二学生,主攻人工智能研究。感谢让我们在CSDN相遇,博主致力于在这里分享关于人工智能,c,Python,爬虫等方面知识的分享。 如果有需要的小伙伴可以关注博主,博主会继续更新的,…...
18、指数移动平均——EMA
简介 在深度学习中,经常会使用EMA(指数移动平均)这个方法对模型的参数做平均,以求提高测试指标并增加模型鲁棒。 指数移动平均(Exponential Moving Average)也叫权重移动平均(Weighted Moving…...
用Go快速搭建IM即时通讯系统
WebSocket的目标是在一个单独的持久连接上提供全双工、双向通信。在Javascript创建了Web Socket之后,会有一个HTTP请求发送到浏览器以发起连接。在取得服务器响应后,建立的连接会将HTTP升级从HTTP协议交换为WebSocket协议。由于WebSocket使用自定义的协议…...
2023年江苏省职业院校技能大赛中职网络安全赛项试卷-学生组-任务书
2023年江苏省职业院校技能大赛中职网络安全赛项试卷-学生组-任务书 2023年江苏省职业院校技能大赛中职网络安全赛项试卷-学生组-任务书第一阶段 (300分) [手敲的任务书 点个赞吧]任务一:主机发现与信息收集 (50分)任务二: 应急响应 (60分)任务三:数字取证与分析(80分)任务四:…...
如何使用码匠连接 MariaDB
MariaDB 是一个免费的、开源的关系型数据库管理系统,由 MariaDB 的创始人 Michael Widenius 于 2010 年创建。它基于 MariaDB,但在对数据存储的处理中加入了一些自己的特性。MariaDB 相对于 MariaDB 而言,具有更好的性能和更好的兼容性&#…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...
