开发者社区> 辰Chen> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

双指针算法

简介: 复习acwing算法基础课的内容,本篇为讲解基础算法:双指针算法,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上
+关注继续查看

文章目录

前言

一、双指针算法概述

二、双指针算法模板及例题

1.模板

2.AcWing799. 最长连续不重复子序列

AC代码

代码分析

3.AcWing 800. 数组元素的目标和

AC代码

代码分析

4.AcWing2816. 判断子序列

AC代码

代码分析

三、时间复杂度


前言

复习acwing算法基础课的内容,本篇为讲解基础算法:双指针算法,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上


一、双指针算法概述

这里的指针不是我们知道的 * ,这里的双指针是例如用 i 和 j 去维护一段区间,大致形式如:

for (int i = 0; i < n; i ++ )
    for (int j = 0; j < i; j ++ )
    {
        ......
    }

二、双指针算法模板及例题

1.模板

本算法模板来自:AcWing算法基础课

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;        //check函数指 i,j之间除了j < i的其他关系

    // 具体问题的逻辑
}

2.AcWing799. 最长连续不重复子序列

本题链接:AcWing799. 最长连续不重复子序列

本博客给出题目截图:

image.png

AC代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N], s[N];

int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    
    for (int i = 0, j = 0; i < n; i ++ )
    {
        s[a[i]] ++;
        while (s[a[i]] > 1)
        {
            s[a[j]] --;
            j ++;
        }
        ans = max (ans, i - j + 1);
    }
    
    printf("%d", ans);
    
    return 0;
}

代码分析

本题利用双指针算法,因为题目保证 a[i] 中的每一个数都是属于[0, 1e5] 的,所以可以用s[a[i]]去存储 a[i] 出现了多少次,每出现一次就把 s[a[i]] ++; 所以如果当 s[a[i]] > 1 的时候就证明出现了重复的数字,本题双指针算法维护的是从 j 开始到 i 结束的这么一段子区间,只要不满足 s[a[i]] > 1 这一条件,j 就不动,i 往后移动一个单位,直到出现了 s[a[i]] > 1,证明维护的这一子区间内出现了重复的元素,我们就把 j 往后移动一位,每次 i 更新的时候都计算一下当前子区间的长度更新 ans.

    for (int i = 0, j = 0; i < n; i ++ )         //因为j始终是小于i的,所以当i走到终点即可
    {
        s[a[i]] ++;
        while (s[a[i]] > 1)
        {
            s[a[j]] --;
            j ++;
        }
        ans = max (ans, i - j + 1);
    }

3.AcWing 800. 数组元素的目标和

本题链接:AcWing 800. 数组元素的目标和

本博客给出本题截图:

image.png

AC代码

#include <cstdio>

using namespace std;

const int N = 100010;

int a[N], b[N];

int main()
{
    int n, m, x;
    scanf("%d%d%d", &n, &m, &x);
    
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    
    for (int i = 0, j = m - 1; i < n; i ++ )
    {
        while (a[i] + b[j] > x) j --;           //这里的while中不需要加 j >= 0,因为保证一定有解
        if (a[i] + b[j] == x)
        {
            printf("%d %d", i, j);
            break;                              //找到目标值就退出,因为保证有唯一解
        }
    }
    
    return 0;
}

代码分析

如下代码会TLE:这个代码就是纯暴力代码了,时间复杂度是O(n²),那么对比我们这个代码和AC的代码,AC的代码优化在哪里了呢?

//错误代码:
   for (int i = 0; i < n; i ++ )
       for (int j = 0; j < m; j ++ )
           if (a[i] + b[j] == x)
           {
               printf("%d %d", i, j);
               exit(0);                          //exit(0); 需要添加头文件 #incldue <cstdlib>
           }

这个错误代码 i 和 j 都是从 0 开始的,而AC的代码中 i 是从0开始的,j 是从 m - 1开始的,即数组a是正序遍历,数组b是逆序遍历,这么遍历的优点在于,因为数组a和数组b都是满足严格上升的,如果满足 i + j > x 的条件,那么 i 是不需要再往后移动的,只需要 j 往前移动就好了,正所谓双向的奔赴要好于单方向的追求,i 和 j 同时向一个值靠近要优于 i 和 j 一直试错的靠近.


4.AcWing2816. 判断子序列

本题链接:AcWing2816. 判断子序列

本博客给出本题截图:

image.png

AC代码

#include <cstdio>

using namespace std;

const int N = 100010;

int a[N], b[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    
    int i = 0, j = 0;
    for (;i < n && j < m; j ++ )
        if (a[i] == b[j]) i ++;
        
    if (i == n) puts("Yes");
    else puts("No");
    
    return 0;
}

代码分析

判断数组a是否是数组b的子序列:

image.png

如图,我们依次对比a数组和b数组的每一个元素,如果不匹配的话,就让数组b向后移动一个单位,如果匹配的话就让数组b和数组a都往后移动一个单位,如果最后a数组的每一个元素在数组b中都有对应元素,则输出Yes,否则输出No

    int i = 0, j = 0;
    for (;i < n && j < m; j ++ )
        if (a[i] == b[j]) i ++;

三、时间复杂度

关于双指针算法的时间复杂度以及证明,后续会给出详细的说明以及证明过程,目前先鸽了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
带你从0->1学习双指针算法
带你从0->1学习双指针算法
39 0
贪心算法
贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法
86 0
算法
算法 大数据 bitmap 排序 桶排序 计数排序 字典序 字符串 字符串匹配 KMP 关键是构造出一个数组, 通过该数据判断从哪一个字符开始匹配 字符串最长的不重复字串 滑动窗口算法, 根据 start 与 end 两个变量锁定一个窗口; 为了进一步提高字符串不重复的查找效...
745 0
算法
https://www.cnblogs.com/lvmylife/p/7208541.html(js常见算法)https://blog.csdn.net/quiet_boy/article/details/53635774 (什么是算法) 什么是算法 算法(algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。
754 0
贪心算法
Leetcode  455 思路: 1、贪心度越低的孩子越容易满足 2、while循环。糖果价值按由小到大匹配贪心度按由小到大排序的孩子,如果最低糖果价值不能满足最低贪心度的孩子,则舍弃该糖果,直到匹配到等价的。
865 0
+关注
辰Chen
CSDN人工智能领域优质创作者,华为云&middot;云享专家,CCF-TYUT President-designate
719
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载