[基础算法](5)双指针
引言
双指针算法是用的很多的一种算法,像做左右端点指针、快慢指针等,其核心思想是让O(n²)的算法优化到O(n)的范围内,在做双指针算法的时候,先考虑暴力做法,是否有单调性存在,然后用双指针优化
常用模板:
for(i=0,j=0;i<n;i++){
while(j<i&&check(i,j)) j++;//判断指针是否在范围内与满足条件
//每道题的具体逻辑
}
最长连续不重复子序列
模板题:799. 最长连续不重复子序列 - AcWing题库
暴力做法:
思路:对每个 i 和 j 都遍历一遍,对每个 i 和 j 都check一下中间的数据是否满足给定的条件,时间为O(n²)
代码:
//check函数
int check(int nums[], int l, int r) {
for (int i = l + 1; i <= r; i++)
for (int j = l; j < i; j++)
if (nums[i] == nums[j])
return 1;
return 0;
}
for (int i = 0; i < n; i++)
for (int j = 0; j <= i; j++)
if (check(nums, j, i) == 0)
res = max(res, i - j + 1);
双指针优化:
暴力法在很多时候是有**重复计算了( i 指针在 j 指针的后面,i 是遍历的整个数组的,j 是遍历 0 到 i 的)
- 比如 j = 0 , i = 5 , 此时发现 i , j 是满条件的;那么后面的 j = 1 到 5 ,i = 5 就不用计算了,肯定是满足条件的
配合代码看
代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 100000
int nums[N];
int sign[N];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&nums[i]);
memset(sign,0,sizeof(sign));
int res=0;
for(int i=0,j=0;j<n;j++){
sign[nums[j]]++;//元素nums[j]出现次数+1
while(sign[nums[j]]>1){ //如果该元素出现的次数要大于1
sign[nums[i]]--;//则以nums[i]结尾的数列长度 -1
i++;
}
if(j-i+1>res) res=j-i+1;
}
printf("%d",res);
return 0;
}
数组元素的目标和
模板题:800. 数组元素的目标和 - AcWing题库
暴力做法
我们可以枚举 a 和 b 中的每一个数 然后 看他们的和是否等于目标,若等于,则返回
代码:
#include<iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
int main() {
int n, m, x;
cin >> n >> m >> x;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
//暴力
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i] + b[i] == x) cout << i << " " << j;
return 0;
}
}
return 0;
}
双指针优化
题目中给出了升序即代表有单调性可循,就可定义左右端点指针,逐渐所有查找区间 时间为O(max(n,m)
代码:
#include<iostream>
using namespace std;
const int N=100010;
int a[N],b[N];
int main()
{
int n,m,x;
cin>>n>>m>>x;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>b[i];
//当a[i]+b[j]>=x时,随着i增加,j减少
for(int i=0,j=m-1;i<n;i++)
{
while(j>=0 && a[i]+b[j]>x) j--;
if(a[i]+b[j]==x)
{
cout<<i<<" "<<j;
return 0;
}
}
return 0;
}
判断子序列
模板题:2816. 判断子序列 - AcWing题库
暴力做法:
我们枚举 a 中的每一位数是否在b中出现过 并且每次遍历b的时候都是在上一个a中元素出现位置的后面,若其中有一次没找到,则直接输出No
#include<iostream>
using namespace std;
int n,m;
const int N = 100010;
int a[N],b[N];
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>b[i];
int k=0;
for(int i=0;i<n;i++){
int j=k;bool f1=false;//j为上一次找寻的末尾,f1标记是否找到
while(j<m) //在[k~m]区间中找 i 是否存在
if(a[i]==b[j++]){
f1=true;
break;
}
if(f1==false){
cout<<"No"<<endl;
return 0;
}
k=j;//更新新的结尾
}
cout<<"Yes"<<endl;
return 0;
}
双指针优化:
从暴力我们可以发现,我们根本不用 a 中每一个数 都重新在 b 中进行找寻,而可以直接扫描一遍 b 数组 若 出现了 a中的次数 则计数+1,最后判断 i 是否等于 n 即可。
代码:
#include<iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
int i, j;
for (i = 0, j = 0; j < m; j++)
if (a[i] == b[j]) i++;
if (i >= n) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}