【算法基础——第七讲】双指针

【算法基础——第七讲】双指针

ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客：​​面向阿尼亚学习​​算法学习笔记系列持续更新中~

文章目录

​​一、前言​​​​二、双指针算法的介绍​​​​三、双指针算法的运用​​

​​1.最长连续不重复子序列​​​​最长连续子序列​​

​​最后​​

一、前言

双指针说是一种算法,其实就是一个​​降低时间复杂度的技巧​​,双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算,熟练的运用双指针算法,可以快速简洁的解决问题.

二、双指针算法的介绍

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向​​（快慢指针）​​​或者相反方向​​（对撞指针）​​的指针进行扫描，从而达到相应的目的。

对撞指针是指在数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如 fast 每次增长两个，slow 每次增长一个。

三、双指针算法的运用

对于一个序列，用两个指针维护一段区间 对于两个序列，维护某种次序。比如归并排序中合并两个有序序列的操作​​​每个双指针算法都由一个朴素算法变化而来​​

// 朴素解法 时间复杂度o(n^2)for (int i = 0; i < n; i++) for (int j = 0; j <= i; j++) if (!check(j, i)) { res = max(res, i - j + 1); }

关于双指针算法的时间复杂度为o(n)：

因为j只初始化了一次，且在过程中，j只增不减

// 双指针算法 时间复杂度o(n)for (int i = 0, j = 0; i < n; i++) { while (j <= i && check(j, i)) j++; res = max(res, i - j + 1);}

由于​​每个双指针算法都由一个朴素算法变化而来​​没有确切的模板,我们直接看题分析双指针算法.

1.最长连续不重复子序列

如下：

//给定一个长度为n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。#include using namespace std;const int N = 1e5+7;int a[N],s[N];//a[N]存储n个整数//s[N]存储每个整数出现的次数int main(){ int n; cin>>n; for (int i = 0; i < n; i ++ ) { cin>>a[i]; } int ans=0; for(int i=0,j=0;i1) { //当a[i]在[i,j]间出现的次数>1时,说明有元素重复了 //左指针j开始移动,当移动到重复的元素时,重复的元素的出现次数就<1了 //循环结束,这时[i,j]区间的元素恢复无重复元素状态 s[a[j]]--; j++; //最长的不包含重复数字的连续子序列的长度 //i-j+1就是[i,j]无重复元素区间的长度 } ans=max(ans,i-j+1);//比较当前[i,j]无重复元素的长度与之前的ans值,取最大 } cout<

最长连续子序列

如下：

/*给定一个长度为 n 的整数序列 a1,a2,…,an。请你找出它的一个最长连续子序列，要求该子序列包含不超过 k 个不同的值。前 6 个测试点满足 1≤k≤n≤10。所有测试点满足 1≤k≤n≤5×105，0≤ai≤106。*/#include #include #include using namespace std;const int N = 5e5+7,M=1e6+7;int n,m;int a[N],cnt[M];int main(){ cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; int res=0,l,r; for(int i=1,j=1,t=0;i<=n;i++)//j在后，i在前 { if(cnt[a[i]]==0)t++;//cnt[]为0，说明没出现过，t + 1 cnt[a[i]]++; //出现次数+1 while(t>m)//不同的值的个数 > k,需要从前开始删数 { if(cnt[a[j]]==1)t--;//cnt[a[j]]为0表示次数出现次数为0，t要-1 cnt[a[j]]--;//最前面一个数出现次数-1 j++;//每次删去最前面的一个数 } if(i-j+1>res)//当前长度比最大长度大,更新一下dis,l和r { res=i-j+1; l=j,r=i; } } cout<

最后

莫言真理无穷尽，寸进自有寸进欢

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。