写点什么

带你从 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
用户头像

卷不死,就往…… 2021.10.19 加入

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

评论

发布
暂无评论
带你从0->1学习双指针算法_5 月月更_秋名山码民_InfoQ写作社区