基础算法--双指针算法
双指针算法
1.基本介绍
严格的来说,双指针只能说是是算法中的一种技巧。
双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。最常见的双指针算法有两种:一种是,在一个序列里边,用两个指针维护一段区间;另一种是,在两个序列里边,一个指针指向其中一个序列,另外一个指针指向另外一个序列,来维护某种次序。


2.模板
for (int i = 0, j = 0; i < n; i ++ ) // j从某一位置开始,不一定是0
{while (j < i && check(i, j)) j ++ ;// 具体问题的逻辑
}
常见问题分类:(1) 对于一个序列,用两个指针维护一段区间,比如快排的划分过程(2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作
双指针算法的核心思想(作用):优化
在利用双指针算法解题时,考虑原问题如何用暴力算法解出,观察是否可构成单调性,若可以,就可采用双指针算法对暴力算法进行优化.
当我们采用朴素的方法即暴力枚举每一种可能的情况,时间复杂度为O(n*n)
for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){//具体逻辑}}
而当我们使用双指针算法时通过某种性质就可以将上述O(n*n)的操作优化到O(n)

暴力算法和它优化后的双指针算法有什么区别:
由于具有某种单调性,朴素算法往往能优化为双指针算法。
区别:
- 朴素算法每次在第二层遍历的时候,是会从新开始(j会回溯到初始位置),然后再遍历下去。(假设i是终点,j是起点)
- 双指针算法:由于具有某种单调性,每次在第二层遍历的时候,不需要回溯到初始位置(单调性),而是在满足要求的位置继续走下去或者更新掉。
3.例题01
先看这样一个例子:输入一个字符每个子串之间有一个空格,让你输出每一个空格后的子串。
输入
abc def hij输出
abc def hij
【参考代码】
#include<iostream>
#include<string>using namespace std;int main()
{string str;getline(cin, str);int n = str.size();for(int i = 0; i < n; i++){int j = i;while(str[j] != ' ') j++;// cout<<j;for(int k = i; k < j; k++) cout<<str[k];cout<<endl;i = j; //循环体执行完后for()中的i才 i++即,下一次开始时 i就到了上一次空格(位置j)的下一位 }return 0;
}

例题02
【AcWing 799. 最长连续不重复子序列 】
给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数(均在 0∼105 范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例:5
1 2 2 3 5输出样例:
3
思路:
使用双指针算法,根据观察发现,当使用i,j两个快慢指针表示当前的指针移动到i的最长不重复序列时候,具有单调性,即i向后移动,j必然向右或者不动,不可能向左移动,这一单调性质导致可以使用双指针算法。(当出现重复时若j还向左移动,那序列必然还有重复,这就矛盾了!)
在双指针算法中,一个指针扫描整个数组而移动,关键如何找到对应的另一个指针移动的位置,在本题中,我们定义i为快指针,j为慢指针,j的位置定义为i对应的最长不重复序列的j的位置,因为不重复,i和j元素都不重复,出现次数都为一,因此我们使用一个数组s来记录各个元素出现的次数,i,j不断移动,数组及时更新,每次i更新,便更新j确保(j,i)区间元素都只出现一次,代码如下
【参考代码】
#include<iostream>using namespace std;
const int N = 100000+10;
int a[N],s[N];// s[N]用来记录数据出现的次数
int main()
{int n;cin>>n;int res = 0;for(int i = 0; i < n; i++) cin>>a[i];for(int i = 0, j = 0; i < n; i++){// 注意:j = 0不能拿下来,不然每次又是从0开始了!s[a[i]]++; // 记录数值a[i]出现的次数// i快指针,j 慢指针while(j <= i && s[a[i]] > 1) // 若出现重复的数值。j <= i不要也行{s[a[j]]--; j++;}//更新的不包含重复的数的连续区间的最大长度res = max(res, i - j +1);}cout<<res;return 0;
}
图解辅助理解:

相关文章:
基础算法--双指针算法
双指针算法 1.基本介绍 严格的来说,双指针只能说是是算法中的一种技巧。 双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针&#…...
企业工程项目管理系统源码(三控:进度组织、质量安全、预算资金成本、二平台:招采、设计管理)
工程项目管理软件(工程项目管理系统)对建设工程项目管理组织建设、项目策划决策、规划设计、施工建设到竣工交付、总结评估、运维运营,全过程、全方位的对项目进行综合管理 工程项目各模块及其功能点清单 一、系统管理 1、数据字典&am…...
生物的神经系统与机器的人工神经网络
生物的神经系统与机器的人工神经网络 文章目录 前言一、人工神经网络二、生物的神经系统三、关系四、相似与区别4.1. 相似:4.2. 区别: 总结 前言 因为本人是学生物的,并且深度学习的核心——人工神经网络与生物的神经系统息息相关,故想要在本…...
JNI 基础
一、JNI 涉及的名词概念 1.1、 JNI:Java Native Interface 它是Java平台的一个特性(并不是Android系统特有的)。实现Java代码调用C/C的代码,C/C的代码也可以调用Java的代码. 1.2、 二进制库分类 : 静态库,动态库. 静态库 系统…...
用户参数(zabbix-agent)
-s 指向被监控端地址 -p 指向被监控端端口 -k 指向key的名字 监控内存使用率 agent vi a.conf server web界面 对数据库的avg进行监控 systemctl 创建监控项 另一台 重启 agent 监控请求数 运行时间 对自定义key的理解 写下想要监控的任何参数命令,利用zabbix…...
期权策略篇: 实现买方狂欢,让卖方稳赚不赔的策略
欢迎来到期权策略篇: 实现买方狂欢,让卖方稳赚不赔的策略,今天给大家带来的期权策略比较简单,是我们比较常见的四种单腿期权策略,这四种策略分别是买入看涨期权、买入看跌期权、卖出看涨期权、卖出看跌期权策略。本文来自…...
关于包,类名,方法名的命名规范
保持与数据库同名的一个命名规范的规则 方法名采用驼峰命名法,保持与数据库同名的一个命名规范的规则 类名采用首字母大写,驼峰命名法,保持与数据库同名的一个命名规范的规则 包名全部使用小写,保持与数据库同名的一个命名规范的规…...
1.1 安装配置CentOS
文章目录 零、学习目标一、导入新课二、新课讲解(一)安装VMWare Workstation1、获取安装程序2、进入安装向导3、按提示完成安装 (二)虚拟网络编辑器1、启动虚拟网络编辑器2、选择VMnet8虚拟网3、更改网络配置4、查看DHCP设置5、查…...
go初识iris框架(七) - 实战资源导入和项目框架搭建
实战项目框架搭建 如下是项目框架搭建后的说明: config::项目配置文件及读取配置文件的相关功能controller:控制器目目录,项目各个模块的控制器及业务逻辑处理的所在目录datasource:实现mysql连接和操作、封装操作mysql数据库的目录。model:数据实体目…...
甲胎蛋白AFP抗体——博迈伦
甲胎蛋白(Alpha-fetoprotein,AFP)是一种由胚胎组织产生的蛋白质,通常以胎儿肝脏和胎盘为主要来源。AFP是一种重要的生物标志物,可用于诊断和预测某些疾病的发展情况。 AFP抗体是指能够与AFP结合的抗体,通常…...
junit.Test误踩坑,识别不到@Test注解,无法运行测试方法
问题的出现源自于下面的一段代码: 在这一段代码中,只看到可以运行的main方法,无法看到test方法可以运行的标志。 只能运行main()方法。 开始排查,对junit包的导入进行检查,发现是没有问题的。 怀疑是否是IntelliJ IDE…...
一加Ace2V/Ace竞速版刷入氧OS13系统-谷歌服务套件-全球语言-国际版体验
截止目前2023年9月5日,一加除了刚上市的Ace2Pro机型未确定国际版以外,其他机型均可以支持氧OS系统刷入。今天我们刷入的就是一加Ace2V和一加Ace竞速版本,两款机型均为MTK天玑处理器,并且系统已经升级了COlorOS13系统,所…...
Java 华为真题-猴子爬山
需求: 一天一只顽猴想去从山脚爬到山顶,途中经过一个有个N个台阶的阶梯,但是这猴子有一个习惯:每一次只能跳1步或跳3步,试问猴子通过这个阶梯有多少种不同的跳跃方式? 输入描述 输入只有一个整数Nÿ…...
Axios笔记
1、Axios介绍 Axios基于promise网络请求库,作用于node.js和浏览器中(即同一套代码可以运行在node.js和浏览器中),在服务器中他使用原生node.js http,在浏览器端则使用XMLHttpRequest。 特性: (1)、支持 Pro…...
如何使用try-except语句处理Python中的异常
在python爬虫行业里面,异常处理能力已经成为了一项非常重要的技能。随着软件规模的不断扩大和复杂性的增加,异常处理能力已经成为了评判一个示波器水平的重要指标。 ,学会使用try-except语句来捕获和处理Python异常,对于我们做爬虫…...
学Python的漫画漫步进阶 -- 第十一步.常用的内置模块
学Python的漫画漫步进阶 -- 第十一步.常用的内置模块 十一、常用的内置模块11.1 数学计算模块——math11.2 日期时间模块——datetime11.2.1 datetime类11.2.2 date类11.2.3 time类11.2.4 计算时间跨度类——timedelta11.2.5 将日期时间与字符串相互转换 11.3 正则表达式模块—…...
发现无尽的创意可能性——Photo Image Editor Pixelstyle for Mac
无论您是一名专业摄影师还是一个爱好者,您都需要一款强大而多功能的图像编辑软件来实现您的创意。Photo Image Editor Pixelstyle for Mac将成为您的创作利器,帮助您探索图像编辑的无限可能性。 Photo Image Editor Pixelstyle for Mac是一款专业级的图…...
Smart Community(1)之设计规范
通过前面大数据开发相关知识的学习,准备做一个项目进行练习---我给他起了一个响亮的名字:基于HadoopHA的智慧社区服务平台 设计规范: 做一个项目之前肯定要先规定一些开发过程中的设计规范 (一)数据埋点规范…...
爬虫工作者必备:使用爬虫IP轻松获得最强辅助
目录 一、爬虫IP的作用与优势 二、选择合适的爬虫IP服务商 三、使用爬虫IP的注意事项和技巧 代码示例 四、合法合规使用爬虫IP 总结 随着互联网的发展,数据已经成为企业竞争的核心资源。而获取这些数据的有效方式,就是通过爬虫技术。但是ÿ…...
工作比读研简单多了
工作比读研简单多了,因为至少有人能解答 工作遇到的问题相比读研时遇到的问题幸福太多,简单太多。因为读研时遇到的更多是未知的问题,是科学问题,是论文中也没有答案的问题,问不着答案,搜不着结果…...
LazyLLM:低代码多智能体应用开发框架实战指南
1. 项目概述:LazyLLM,一个为懒人开发者准备的多智能体应用构建工具如果你和我一样,在尝试构建一个基于大语言模型的智能应用时,感到头大——不是被各种框架的API调用搞晕,就是被模型部署、服务编排、数据流设计这些工程…...
关于python中打开文件,以及可能错误,介绍
**该mode是基于open()函数里参数的调整** 错误代码 f r"C:\dj\dw1.txt" b f.read(c) print(b) f.close() 正确代码 f open(r"C:\dj\dw1.txt") s f.read() print(s) f.close()open()函数需要后面的打开路径,r/R表示该代码的的原意 mode…...
NAND闪存市场演进:从消费电子到AI时代的技术博弈与产业洞察
1. 从一篇旧闻说起:NAND闪存市场的“过山车”与底层逻辑最近在整理资料时,翻到一篇2012年的行业旧闻,标题是《平板电脑需求推动NAND闪存增长》。文章的核心观点很明确:以智能手机、平板电脑(当时还是iPad和安卓平板争锋…...
本地AI网关实战:统一管理多模型服务,实现智能路由与成本控制
1. 项目概述:一个本地化的AI网关如果你正在同时使用多个AI模型服务商,比如OpenAI、Anthropic、Google Gemini,或者还在本地运行着Ollama、vLLM这样的模型,那你一定体会过那种切换的繁琐。每个客户端、每个脚本都要配置不同的API密…...
独立开发者实战:AI编程的泥泞战壕与生存指南
1. 从“氛围编程”到真实战场:一个独立开发者的自白如果你最近也在关注独立开发或者AI编程工具,那你一定听过“氛围编程”这个词。它听起来很酷,对吧?仿佛你只需要对着AI描述一下心中的“氛围感”,一个完美的应用就能应…...
主动悬架乘坐舒适性控制策略优化【附模型】
✨ 长期致力于随机路面、主动悬架、乘坐舒适性、控制策略、仿真分析研究工作,擅长数据搜集与处理、建模仿真、程序编写、仿真设计。 ✅ 专业定制毕设、代码 ✅如需沟通交流,点击《获取方式》 (1)随机路面与1/4悬架动力学建模&…...
基于eBPF的系统调用监控:原理、部署与性能调优实战
1. 项目概述:一个“无人值守”的系统调用监控器最近在折腾系统性能分析和安全监控,发现了一个挺有意思的开源项目:syscalldev/nohuman。这个名字直译过来是“无人”,听起来有点神秘,但其实它的核心功能非常直接——一个…...
(5月最新版)OpenClaw 小龙虾 Windows 一键安装与问题排查
OpenClaw(小龙虾)Windows 11 一键部署教程|2026 新版|零代码・免配置・解压即用 适用系统:Windows 11 专业版 / 家庭版 / 正式版(全版本兼容)当前版本:v2.7.1 下载地址:…...
从HEX到芯片:使用J-Flash实现高效固件烧录与生产级加密
1. 认识J-Flash:你的芯片烧录好帮手 第一次接触J-Flash时,我正为一个量产项目发愁——需要给500片GD32F103烧录固件。手动用IDE一个个烧?效率太低;找代工厂?成本太高。直到同事推荐了J-Flash,我才发现原来烧…...
Axolotl与LLaMA-Factory对比:架构与扩展性分析-方案选型对比
1. 问题背景与选型目标 在大型语言模型(LLM)落地的浪潮中,“微调”已从少数研究团队的实验行为,变为大量中小企业甚至个人开发者的刚需。业务团队不再仅仅使用 API 调用闭源模型,而是希望基于开源基座模型(…...
