[基础算法](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;
}

本文链接：