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

初识算法 · 双指针(3)

目录

前言:

和为s的两数之和

题目解析:

​编辑

算法原理:

算法编写:

三数之和

题目解析

算法原理

算法编写


前言:

本文通过介绍和为S的两数之和,以及三数之和,对双指针算法进行深一步的了解,介绍该算法博主使用三部曲,第一步对题目进行分析,里面会夹杂着暴力解法的问题,第二步对于算法原理进行分析,第三步则是对算法进行编写,最后分析时间复杂度,可能会分析空间复杂度。

题目的链接为:

LCR 179. 查找总价格为目标值的两个商品 - 力扣(LeetCode)

15. 三数之和 - 力扣(LeetCode)

那么话不多说,进入正题吧!


和为s的两数之和

题目解析:

该题目的要求是找到两个数,这两个数相加的和是等于target的。题中也有个很重要的条件,按照升序记录于数组中,这个升序是十分关键的。我们直接探讨暴力解法,即将所有的两数之和举例出来,第一次相等就返回即可,如果运气差点,就需要遍历完整个数组两次,即两个for循环,此时的时间复杂度为O(N^2),这是暴力解法,是比较容易想出来的:

for (int i = 0; i < price.size();i++)
{for (int j = 0;j < price.size();j++){//判断是否满足条件}
}

当然了,如果使用暴力解法,那么我们对题目的升序就没有任何使用了,就很吃亏,所以现在进入算法原理。

算法原理:

使用双指针算法,对于题目中的升序,一定要利用好,我们知道:

target = num1 + num2

那么既然是升序的,如果我们让两个指针,一个从开始走,一个从末尾走,也就是最大的和最小的走,判断结果,大于了target,右指针往左边走,反之亦然,这时候其实已经做完题目了。

对于循环来说,只有一个循环,如果没有找到,返回的是个空就可以。

算法编写:

class Solution 
{
public:vector<int> twoSum(vector<int>& price, int target) {int right = price.size() - 1, left = 0;while(left < right){if(price[left] + price[right] == target)return {price[left],price[right]};else if(price[left] + price[right] < target) left++;else if(price[left] + price[right] > target) right--;}return { };}
};

结束条件自然是左小于右,因为返回的是vector,都没有找到的话返回空即可,时间复杂度是O(N),没有新开空间,所以空间复杂度为O(1)。


三数之和

题目解析

由题目可得,找三个数,其中这三个数相加等于0,我们不妨将题目理解为,找一个数,该数 = 另外两数之和,是不是就感觉容易多了?不过是上文和为s的变种而已,我们只是需要将S变化一下即可。

以上是题目的最基本的要求,那么还有一个要求是,不允许出现重复的,这是和本文第一道题不同的要求,这点代表了我们要去重即可。

那么同样的,我们思考如何暴力解法?

暴力解法无非是将所有的三元组列出来,判断和是否为零,满足条件,我们可以将它丢进set,用set本身的性质进行去重即可。

但是暴力解法的时间复杂度可就高了,三个数都要单独列出,也就是需要三个循环,时间复杂度为O(N^3),往往是通过不了的。

所以,我们进入到算法原理方面。


算法原理

我们同样的使用双指针算法,因为是双指针不是三指针,所以需要我们固定一个数,用来充当target,有了第一个题目的经验,我们不妨排序一下,保证数组有序的同时有利于我们控制指针变量,排序之后对于我们去重的操作也会容易很多。

排序之后,固定好target,然后进入到第二个循环,通过双指针算法,找两个数,使该三个数相加等于0即可。

那么指针移动分为两种情况,如果前面两个数相加>target,代表right大了,需要right--,反之亦然,这是移动的情况。满足条件的话,添加进去就可以了。

那么最重要的点来了,我们如何进行去重操作呢?

判断的是nums[left] == nums[left + 1]是否相等即可,如果相等了,left就++,right同理,但是去重的不只有这两个数,还有一个数也需要去重,就是nums[i],如果i不去重,肯定是很导致很多重复的元素,毕竟都是会从头开始找的。

去重i的时候,需要控制i的移动,因为去重操作本身就会控制指针移动。


算法编写

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ans;sort(nums.begin(),nums.end()); for(int i = nums.size() - 1;i > 1 && nums[i] >= 0;){int target = nums[i];int left = 0,right = i - 1;while(left < right){if(nums[left] + nums[right] > (-target)) right--;else if(nums[left] + nums[right] < (-target)) left++;else{ans.push_back({nums[left++],nums[right--],nums[i]});while(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}}i--;while(i < nums.size() && nums[i] == nums[i + 1]) i--;}return ans;}
};

三个去重,一个排序,三个判断,最后返回即可。


感谢阅读!

相关文章:

初识算法 · 双指针(3)

目录 前言&#xff1a; 和为s的两数之和 题目解析&#xff1a; ​编辑 算法原理&#xff1a; 算法编写&#xff1a; 三数之和 题目解析 算法原理 算法编写 前言&#xff1a; 本文通过介绍和为S的两数之和&#xff0c;以及三数之和&#xff0c;对双指针算法进行深一步…...

【AI知识点】近似最近邻搜索(ANN, Approximate Nearest Neighbor Search)

近似最近邻搜索&#xff08;ANN, Approximate Nearest Neighbor Search&#xff09; 是一种用于高维数据检索的技术&#xff0c;目标是在给定查询的情况下&#xff0c;快速找到距离查询点最近的数据点&#xff0c;尽管结果可能并不完全精确。这种方法特别适用于高维数据&#x…...

编程工具简介

在编程工作中&#xff0c;选择合适的工具确实能够显著提升工作效率。以下是一些被广泛推荐的工具&#xff1a; 1. Visual Studio Code (VS Code)&#xff1a;这是一款轻量级但功能强大的代码编辑器&#xff0c;支持多种编程语言&#xff0c;拥有丰富的插件生态系统&#xff0…...

汽车信息安全 -- 存到HSM中的密钥还需包裹吗?

目录 1.车规芯片的ROM_KEY 2.密钥加密与包裹 3.瑞萨RZ\T2M的密钥导入 4.小结 在车控类ECU中&#xff0c;我们通常把主控芯片MCU中的HSM以及HSM固件统一看做整个系统安全架构的信任根。 所以大家默认在HSM内部存储的数据等都是可信的&#xff0c;例如CycurHSM方案中使用HSM…...

【PostgreSQL】入门篇——SELECT、INSERT、UPDATE 和 DELETE 语句,SQL 中最常用的四种操作用法

1. SELECT 语句 描述 SELECT 语句用于从数据库中查询数据。可以选择特定的列或所有列&#xff0c;并可以通过条件过滤结果。 语法 SELECT column1, column2, ... FROM table_name WHERE condition;示例 假设我们有一个名为 employees 的表&#xff0c;结构如下&#xff1a…...

【Ubuntu】安装常用软件包-mysql

我的几个服务是部署在docker的同一个网络里&#xff0c;这样相互访问就可以通过docker容器的名字访问&#xff0c;比如容器A访问容器B&#xff0c;就可以http://B:8080/xxx 这样访问&#xff0c;不用关心ip是多少。 所以mysql前面文章给安装到主机里&#xff0c;感觉有点坑自己…...

幂等性及技术解决方案

文章目录 定义幂等性 为什么需要幂等性幂等性设计注意事项幂等性的范围分布式锁解决幂等性 设计 延伸阅读 定义幂等性 简单地说&#xff0c;我们可以多次执行幂等运算而不改变结果或者使用相同的输入参数中被调用多次&#xff0c;则不具有额外效果的操作&#xff0c;也就是多…...

正向代理 反向代理

正向代理 正向代理是一种网络服务&#xff0c;它作为客户端和目标服务器之间的中间人&#xff0c;代表客户端向目标服务器发送请求并接收响应。以下是关于正向代理的详细解释&#xff1a; 工作原理 客户端配置&#xff1a; 客户端&#xff08;如浏览器&#xff09;配置为使用…...

【分布式微服务云原生】如何在ActiveMQ中优雅处理提前支付的延时订单

摘要 本文将深入探讨在ActiveMQ中如何处理用户提前支付的延时订单问题。我们将介绍如何通过更新订单状态、检查延迟任务、取消延迟消息、使用死信队列、消息选择性消费、设置合理的超时时间以及及时反馈和日志记录等策略&#xff0c;来确保系统的一致性和及时响应用户操作。文…...

Easy Excel从入门到精通!!!

目录 1.文件导入 1.1基本方式读取excel文件内容 1.2注解模型映射器读取excel 1.3多行表头读取 1.4文件上传读取 2.文件导出 2.1基本方式导出 2.2模型映射导出 2.3设置行高、列宽等内容 2.4合并单元格 2.5导出设置超链接、批注、公式 2.6模板填充对象导出 2.7模板填…...

简易CPU设计入门:取指令(三),ip_buf与rd_en的非阻塞赋值

在开篇&#xff0c;还是请大家首先准备好本项目所用的源代码。如果已经下载了&#xff0c;那就不用重复下载了。如果还没有下载&#xff0c;那么&#xff0c;请大家点击下方链接&#xff0c;来了解下载本项目的CPU源代码的方法。 下载本项目代码 准备好了项目源代码以后&…...

【算法】---归并排序(递归非递归实现)

参考 左程云算法 算法导论 前言 本篇介绍 归并排序分治法 前置知识 了解递归&#xff0c; 了解数组。 引入 归并排序 归并排序最早是由公认的现代计算机之父John von Neumann发明的&#xff0c; 这是一种典型的分治思想应用。 我们先介绍分治思想 分治思想 分治思想的…...

UniVue大版本更新:UniVue2.0.0-preview

大版本发布说明 距离上次更新好像已经过去很久了&#xff0c;最近太忙了没时间维护新版本&#xff0c;也是自己在使用的过程中发现了很多问题也有了更多的灵感&#xff0c;由于和之前的版本区别太大&#xff0c;决定重新开一个大版本。这个UniVue2之后的版本追求是性能&#xf…...

RabbbitMQ篇(环境搭建 - 下载 安装)(持续更新迭代)

目录 一、Windows 1. 下载安装程序 2. 安装配置erlang 3. 安装rabbitMQ 4. 验证 二、Linux 1. 下载rpm包 1.1. 下载Erlang的rpm包 1.2. 下载socat的rpm包 1.3. 下载RabbitMQ的rpm包 2. 安装 2.1. 安装Erlang 2.2. 安装socat 2.3. 安装RabbitMQ 3. 启动RabbitMQ服…...

C++基础补充(02)C++其他控制语句break continue goto等

文章目录 1. break2. continue 语句3. goto 语句goto的存在 4. 跳出多重循环4.1 goto 直接跳转4.2 C11及其后版本的 return 语句4.3 使用标志变量 在C中&#xff0c;控制语句用于管理程序的执行流程。常见有 break、continue 和 goto。 1. break break语句主要用于在循环或者s…...

决策树中联合概率分布公式解释说明

学习决策树时书本中有一公式 7-3 是&#xff1a; P ( X x i , Y y j ) p i j ( i 1 , 2 , … , m , j 1 , 2 , … , n ) P(X x_i, Y y_j) p_{ij} \quad (i 1, 2, \dots, m, \ j 1, 2, \dots, n) P(Xxi​,Yyj​)pij​(i1,2,…,m, j1,2,…,n) 这个公式表示的是随机变…...

计算机毕业设计 农场投入品运营管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…...

php email功能实现:详细步骤与配置技巧?

php email发送功能详细教程&#xff1f;如何使用php email服务&#xff1f; 无论是用户注册、密码重置&#xff0c;还是订单确认&#xff0c;电子邮件都是与用户沟通的重要手段。AokSend将详细介绍如何实现php email功能&#xff0c;并提供一些配置技巧&#xff0c;帮助你更好…...

MapBox Android版开发 6 关于Logo

MapBox Android版开发 6 关于Logo Logo的显示查看源码及思路&#xff08;Logo&#xff09;第一步第二步 隐藏Logo示例查看源码及思路&#xff08;Info&#xff09;第一步第二步 隐藏Logo和Info示例 看到有网友留言问如何移除Logo&#xff0c;今天看了下V9源码&#xff0c;发现M…...

2024年房市

24年8月15日&#xff0c;国家统计局公布&#xff0c;“7月末&#xff0c;商品房待售面积73926万平方米”。(原文链接&#xff1a;https://www.stats.gov.cn/sj/zxfb/202408/t20240815_1955982.html)   7.39亿平方存量商品房&#xff0c;估价均价1万每平&#xff0c;总价约&am…...

index索引

index索引&#xff1a; create index 【1】on 【2】(【3】) 1为索引名&#xff0c;通常为id_表名_列名。2为表名。3为列名。 CREATE INDEX id_account_id ON account(id); -- 根据id创建索引 CREATE INDEX id_account_idname on account(id,name); -- 创建组合索引 索…...

理解互联网链路:从本地ISP到Tier 1 ISP运营商

1. 互联网服务提供商&#xff08;ISP&#xff09; 互联网服务提供商&#xff08;ISP&#xff09;是指提供互联网接入服务的公司或组织。它们负责将用户连接到互联网&#xff0c;并提供相关的服务&#xff0c;如电子邮件、网站托管和其他在线服务。ISP可以分为不同的层级&#…...

基于元神操作系统实现NTFS文件操作(三)

1. 背景 本文主要介绍DBR的读取和解析&#xff0c;并提供了基于元神操作系统的实现代码。由于解析DBR的目的是定位到NTFS磁盘分区的元文件$Root进行文件操作&#xff0c;所以只解析了少量的部分&#xff0c;其它部分可以参考相关文档进行理解。 DBR存在于磁盘分区的第一个扇区…...

深度学习与数学归纳法

最近发现&#xff0c;深度学习可以分为两个主要的阶段&#xff0c;分别是前向推理以及反向传播&#xff0c;分别对应着网络的推理和参数训练两个步骤。其中推理有时候也称为归纳推理。 在做参数训练的时候&#xff0c;本质上是在利用历史数据求网络参数的先验分布&#xff1b; …...

《Linux从小白到高手》理论篇(六):Linux软件安装一篇通

List item 本篇介绍Linux软件安装相关的操作命令&#xff0c;看完本文&#xff0c;有关Linux软件安装相关操作的常用命令你就掌握了99%了。 Linux软件安装 RPM RPM软件的安装、删除、更新只有root权限才能使用&#xff1b;查询功能任何用户都可以操作&#xff1b;如果普通用…...

【Spring】运行Spring Boot项目,请求响应流程分析以及404和500报错

1. 运行项目 import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; SpringBootApplication public class Application { public static void main(String[] args) { SpringApplication.run(Appl…...

②EtherCAT转Modbus485RTU网关多路同步高速采集无需编程串口服务器

EtherCAT转Modbus485RTU网关多路同步高速采集无需编程串口服务器https://item.taobao.com/item.htm?ftt&id798036415719 EtherCAT 串口网关 EtherCAT 转 RS485 &#xff08;接上一章&#xff09; 自由协议通信步骤 &#xff08;以MS-A2-1041为例&#xff09; 接收与…...

matlab-对比两张图片的HSV分量的差值并形成直方图

%对比两张图片的HSV分量的差值并形成直方图&#xff0c;改个路径就能用&#xff0c;图片分辨率要一致 close all; clear all; clc; I1imread(E:\test\resources\image\1.jpg); I2imread(E:\test\resources\image\2.jpg); HSV1 rgb2ntsc(I1); HSV2 rgb2ntsc(I2); %HSV,HSV 代…...

微服务SpringGateway解析部署使用全流程

官网地址&#xff1a; Spring Cloud Gateway 目录 1、SpringGateway简介 1、什么是网关 2、为什么用网关【为了转发】 2、应用&#xff1a; 1.启动nacos 2.创建网关项目 3.网关配置1 4.网关配置2【了解】 5.过滤器配置【了解】 1、SpringGateway简介 核心功能有三个&…...

Solidity 存储和内存管理:深入理解与高效优化

在 Solidity 中&#xff0c;存储和内存管理是编写高效智能合约的关键组成部分。合约执行的每一步操作都可能涉及到数据的存储和读取&#xff0c;而这些操作对 gas 的消耗有很大影响。因此&#xff0c;理解 Solidity 的存储模型以及如何优化数据的管理对于合约的安全性、性能和成…...

wordpress文件路径/网站优化分析

1. 5W1H 分析法 解决事件 Who (谁来做&#xff09; When?&#xff08;何时做&#xff09; Where?&#xff08;何地做&#xff09; What? &#xff08;做什么&#xff09; Why? &#xff08;为什么做&#xff09; How? &#xff08; 怎么做&#xff09;。 5W1H 思考点人W…...

wordpress nextapp插件/网络软文推广网站

录屏大师 视频导出 问题描述 今天因为一些原因&#xff0c;需要把直播视频录制下来&#xff0c;下载了录屏大师。等我录制完毕之后&#xff0c;突然发现在自己的文件管理里没有找到相应的视频。诶&#xff01;我就纳闷了&#xff0c;不是录下来了&#xff0c;在 app 里也可以…...

著名的设计网站/seo入门基础知识

1,首先确保hadoop和spark已经运行。&#xff08;如果是基于yarn&#xff0c;hdfs的需要启动hadoop,否则hadoop不需要启动&#xff09;。 2.打开idea&#xff0c;创建maven工程。编辑pom.xml文件。增加dependency. <dependency> <!-- Spark dependency --> <grou…...

典型网站建设/四川专业网络推广

在原版ubuntu安装Wildfire.v3.0.M020.for.Linux一 准备工作1 安装csh 或 tcshsudo apt-get install csh或sudo apt-get install tcsh2 安装 libmotif3、 libstdc2.10-glibc2.2sudo apt-get install libmotif3 libstdc2.10-glibc2.23用新立得安装gkt1.2(如果系统已经安装的话&am…...

赤水市建设局官方网站/广告网页

尊重知识版权&#xff1a;http://imysql.com/2015/06/10/mysql-faq-processlist-thread-states.shtml 一般而言&#xff0c;我们在processlist结果中如果经常能看到某些SQL的话&#xff0c;至少可以说明这些SQL的频率很高&#xff0c;通常需要对这些SQL进行进一步优化。 今天我…...

电子商务网站建设需求说明书/如何优化搜索引擎的准确性

给出集合 [1,2,3,…,n]&#xff0c;其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况&#xff0c;并一一标记&#xff0c;当 n 3 时, 所有排列如下&#xff1a; “123” “132” “213” “231” “312” “321” 给定 n 和 k&#xff0c;返回第 k 个排列。 示例 1&…...