带你从 0-＞1 学习双指针算法

2022 年 5 月 10 日
本文字数：549 字
阅读完需：约 2 分钟

为啥要用双指针？

先试想一下，如果用 BF 来解题

for(i = 0;i < len; i++)  for(j = 0;j <= i; j++)    if(check（——）)

复制代码

时间复杂度为 O(n^2)，没有进行优化，如果数列为单调，（sort 后必然单调）可以使用双指针优化，所以核心思想：将 BF 算法 O(n^2)=>双指针 O(n)在我理解，只要是这种的优化都可以称之为双指针算法

模板实现

for(i = 0,j = 0;i < n;i++){  while(j < i && check(i,j))    j++;  //根据题目来看}

复制代码

题目：最长不连续子序列

BF 算法：

for(int i = 0;i < n; i++)  for(int j = 0; j <= i; j++)    if(check(j,i))    {      res = max(res,j - i + 1);//更新最大的，即为最长    }

复制代码

双指针算法：

for(int i=0,j=0;i<n;i++){  while(j<=i&&check(j,i))  j++;  res=max(res,j-i+1);}

复制代码

先写 bf 算法，然后通过 i，j 之间的单调关系来优化，从而写出双指针算法

#include<iostream>using namespace std;const int N = 100010;int n;int a[N],s[N];int main(){    cin>>n;    for(int i=0;i<n;i++)    cin>>a[i];    int res = 0;    for(int i=0,j=0;i<n;i++)    {        s[a[i]]++;//简单的哈希        while(s[a[i]]>1)        {            s[a[j]]--;            j++;        }        res = max(res,i-j+1);    }    cout<<res;    return 0;}

复制代码

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/23ec121355141674a2829c5b0】。

秋名山码民

关注

卷不死，就往…… 2021.10.19 加入

2019NOIP退役成员，华为云享专家，阿里云专家博主，csdn博主，努力进行算法分享，有问题欢迎私聊

发布

暂无评论

创作场景

带你从 0-＞1 学习双指针算法

为啥要用双指针？

模板实现

秋名山码民

评论