代码编织梦想

一、双指针算法详解

1. 双指针算法介绍

  • 双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向或者相反方向的指针进行扫描,从而达到相应的目的。
  • 在前文所介绍的快速排序和归并排序也是双指针算法的一种。
  • 每当遇到双指针问题时,都可以先通过暴力方法尝试解决问题,然后发现其中存在的一些性质,再用双指针算法进行优化。

2. 双指针算法常见套路

  • 双指针的初始位置。根据双指针的分类,有两种可能。
  • 双指针的移动方法。根据双指针的分类,有两种可能。
  • 遍历的结束条件。根据双指针的分类,有两种可能。

3. 双指针算法作用

  • 朴素算法每次在第二层遍历的时候,是会从新开始( j 会回溯到初始位置),然后再遍历下去。(假设i是终点, j 是起点)
  • 双指针算法:由于具有某种单调性,每次在第二层遍历的时候,不需要回溯到初始位置(单调性),而是在满足要求的位置继续走下去或者更新掉。
  • 因此,双指针算法主要起优化的功能,例如当我们使用朴素方法即暴力枚举每一个可能的情况时,时间复杂度为 O(n*n)
    在这里插入图片描述

此时,我们使用双指针算法利用就可以将 O(n*n) 优化为 O(n)
在这里插入图片描述

4. 具体应用

4.1 数组里的双指针

用暴力解法一定可解,双重循环得出结果。使用双指针的方法,可以借助一个额外变量,实现降维优化。

(1)相反方向运动

  • 两个指针在数组的头和尾,都往中间移动,直到相遇。
  • 两个指针在数组的中间,往数组的两端移动,直到到达边界。
  • 每次循环时,我们值比较当前的两个元素,在这两个元素当中,求出对应的结果。

(2)相同方向运动

  • 两个指针均在数组的一端,都往另一端移动,直到满足条件为止。
  • 两个指针的移动速度不同,类似于滑动窗口问题,快指针一直往前遍历,走到尾部则循环结束,慢指针视条件进行移动。
  • 每次循环时,看子区间是否满足某个条件,子区间是由双指针框起来, 输出的是子区间的变形。

4.2 双指针算法与前缀和

  • 二者均是对子区间进行操作,因此有一定的结合可能。
  • 前缀和是需要用到子区间和时,通过借助一个数组,去存储前缀和。

4.3 链表里的双指针

  • 以快慢指针为主,快指针一次 2 步,慢指针一次 1 步等等。
  • 典型例题:在链表当中找一个环,有环的话,快慢指针必定会相遇,若无环的话,则快指针就直接走到结尾。

5. 举例说明

关于具体算法应用大家可以看我的快速排序和归并排序,都是非常典型的双指针问题。

二、双指针算法例题

1. 最长连续不重复子序列

题目描述

给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。

输入格式

输入共两行。
第一行包含整数 n。
第二行包含 n 个整数(均在 0∼1e5 范围内),表示整数序列。

输出格式

共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。

数据范围

1≤n≤100000

输入样例

5
1 2 2 3 5

输出样例

3

具体实现

实现思路

在这里插入图片描述

  • 绿色指针表示他最左可以到什么位置,使得绿色指针和红色指针没有重复数字,每次将红色指针向右移动一个位置,然后重新求绿色指针最靠左的话可以再什么位置,每次都要进行匹配。
  • 每当红色指针向右走时,绿色指针也必定向右走。假如说红色指针往右走一个位置时,绿色指针往左走就会矛盾,因为,移动后的绿色指针和红色指针没有重复元素的话,那么在红色指移动之前绿色指针所处的位置就不是最左端,一个没有重复区间内部的子区间内部都是没有重复元素的
  • 只需要每次枚举红色指针,通过绿色指针的位置在红色位置的左边和检查绿色指针和红色指针之间有没有重复元素,然后判断绿色指针是否需要向右移动。
  • 时间复杂度从 O(n*n) 优化为 O(n)

辅助图解

在这里插入图片描述

代码注解

  • s[N] 用来记录每个数据出现的次数,要确保所求区间内部每个元素都只出现一次。
  • i 可看作上述思路的红色指针,j 可看作上述的绿色指针。

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n;
int q[N], s[N];
int main()
{
    cin>>n;
    for (int i = 0; i < n; i ++ )
    {
        cin>>q[i];
    }
    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ )
    {
        s[q[i]] ++ ;
        while (j <= i && s[q[i]] > 1) 
        {
            s[q[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res << endl;
    system("pause");
    return 0;
}

2. 数组元素的目标和

题目描述

给定两个升序排序的有序数组 A 和 B,以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i] + B[j] = x 的数对 (i,j)。
数据保证有唯一解。

输入格式

输入共三行。
第一行包含三个整数 n,m,x,分别表示 A 的长度,B 的长度以及目标值 x。
第二行包含 n 个整数,表示数组 A。
第三行包含 m 个整数,表示数组 B。

输出格式

共一行,包含两个整数 i 和 j。

数据范围

数组长度不超过 1e5。
同一数组内元素各不相同。
1 ≤ 数组元素 ≤ 1e9

输入样例

4 5 6
1 2 4 7
3 4 6 8 9

输出样例

1 1

具体实现1——暴力法

实现思路

  • 通过两个单独的 for 循环对 A 和 B 两个数组内的元素进行输入。
  • 通过两个 for 循环对每个数组当中的每个元素进行遍历,并判断是否等于目标值,若等于,输出此时的 i ,j 坐标。
  • 暴力法可以解决问题,但是会 超时
  • 时间复杂度为 O(mn)

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int A[N],B[N];
int n,m,x;
int main()
{
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
    }
    for(int j=0;j<m;j++)
    {
        cin>>B[j];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(A[i]+B[j]==x)
            {
                cout<<i<<" "<<j<<endl;
            }
        }
    }
    system("pause");
    return 0;
}

具体实现2——双指针算法

实现思路

  • 寻找单调性,对暴力做法进行优化。
  • 对于每一个 i 都想找到一个 j 使得 A[i] + B[j] = x,由于两段序列都是单调递增的,因此,我们让 j 从 m-1 位置开始(从右往左扫描),根据单调性,一旦 A[i] + B[j] > x,当前 i 位置的下一个 A[i] :必定会有 A[i] + B[j] > x,那么 j 就左移 j-- 。直到出现 A[i] + B[j] < x 时,将 i 右移 i++,此时,j 保持不动,一直移动 i 进行判断,直到 A[i] + B[j] = x 时,输出结果。注:j 是从下标 m-1 位置开始往左移的,即还要满足 j>=0。
  • 就好比两个数组,当大于时移动其中一个,小于时移动其中另一个。
  • 时间复杂度为 O(n)

输入样例演示

ij判断是否为6
19大于
18大于
17大于
16大于
14小于
24等于

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, x;
int A[N], B[N];
int main()
{
    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, j = m - 1; i < n; i ++ )
    {
        while (j >= 0 && A[i] + B[j] > x)
        {
            j -- ;
        }
        if (j >= 0 && A[i] + B[j] == x) 
        {
            cout << i << ' ' << j << endl;
        }
    }
    system("pause");
    return 0;
}

3. 判断子序列

题目描述

给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列,例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

输入格式

输入共三行。
第一行包含两个整数 n,m。
第二行包含 n 个整数,表示 a1 , a2 ,…, an
第三行包含 m 个整数,表示 b1 , b2 ,…, bm

输出格式

如果 a 序列是 b 序列的子序列,输出一行 Yes。
否则,输出 No。

数据范围

1 ≤ n ≤ m ≤ 1e5
−1e9 ≤ ai , bi ≤ 1e9

输入样例

3 5
1 3 5
1 2 3 4 5

输出样例

Yes

具体实现

实现思路

  • 判断子序列,顺次判断。
  • j指针用来扫描整个 b 数组,i 指针用来扫描 a 数组。若发现 a[i] == b[j] ,则让 i 指针后移一位。
  • 整个过程中,j 指针不断后移,而i指针只有当匹配成功时才后移一位,若最后若i==n,则说明匹配成功。
  • 但凡存在一种匹配方式,那么我们的双指针算法一定可以找到。

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, m;
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 i = 0, j = 0;
    while (i < n && j < m)
    {
        if (a[i] == b[j]) 
        {
            i ++ ;
        }
        j ++ ;
    }
    if (i == n) 
    {
        puts("Yes");
    }
    else 
    {
        puts("No");
    }
    system("pause");
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45891612/article/details/127993189

基础算法-学习整理-1_growthdiary007的博客-爱代码爱编程

说明:为了方便以后复习,建立第一个目录,暂时整理这些,以后会继续整理,如有不当之处,欢迎指正批评哦。 (为什么要分文章建目录?发现文章变长之后,CSDN支持体验不佳,编辑起来很卡) 基础算法-学习整理-1 LeetCode

数据结构与算法基础-----链表的结点-爱代码爱编程

单链表: 结点只有一个指针域的链表双链表: 结点有两个指针域的链表循环链表: 首尾相接的链表头指针、头节点、首元结点:头指针:指向链表中第一个结点的指针 头结点:是在链表首元结点之前附设的一个结点,并不是链表的第一个结点 首元结点:是指链表中存储第一个数据元素的结点 一、如何表示空表? 无头结点时,头指针为空表示空表。 有头结点时,头结点的指针域为

十大经典排序算法-快速排序算法详解-爱代码爱编程

十大经典排序算法 十大经典排序算法-冒泡排序算法详解十大经典排序算法-选择排序算法详解十大经典排序算法-插入排序算法详解十大经典排序算法-希尔排序算法详解十大经典排序算法-快速排序算法详解十大经典排序算法-归并排序算法详解十大经典排序算法-堆排序算法详解十大经典排序算法-计数排序算法详解十大经典排序算法-桶排序算法详解十大经典排序算法-基数排序算法详解一

算法系列--滑动窗口与双指针-爱代码爱编程

简述个人理解滑动窗口与双指针: 双指针:以r为基础指针并根据题目要求来移动l或者保持l不动,同时ans由每一步的r-l来更新。 滑动窗口:以l为基础指针,并且l~r看做一个窗口,r不断右移,根据题目要求来右移一次l或者保持l不动,特点是r-l始终不减,ans为最终的r-l 区别:双指针算法当需要移动l指针时,可能移动多个单位以满足要求。而滑动窗口算法

基础算法(一)零基础学算法---总结大篇-爱代码爱编程

基础算法(一) 纯干货!! 排序及二分算法 码了7天,手残党也能看懂!! 手残第一篇:第一章 基础算法(一) 提示:你的三连是作者输出下去的动力哦!!真的真的!!!(小声哔哔:赶紧收藏!!内容持续更新中。。。) 文章目录【算法篇】 基础算法(一) 纯干货!! 排序及二分算法前言一、排序1.快速排序 quick_sort2.归并排序 merge

算法总结:双指针算法(什么时候该使用、如何使用)-爱代码爱编程

算法总结:双指针算法的理解和使用思路 简介一:从一个C++语言程序开始1.基础解法2.双指针解法二:Leetcode实战总结注 简介 双指针算法指的是在重复遍历对象的过程中,不是在两个循环中使用单个指针进行重复访问,而是在一个循环中使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行访问。 一:从一个C++语言程序开始 给你 n

算法——双指针-爱代码爱编程

目录 一、前言 二、算法核心思想 三、算法模型 1.对撞指针 2.快慢指针 3.滑动窗口 4.归并排序 四、总结 一、前言 双指针是一种应用很广泛且基础的算法,严格来说双指针不是算法更像是一种思想。双指针中的“指针” 不仅仅是大家所熟知的C/C++里面的地址指针,还是索引、游标。本文将会简单介绍双指针及双指针的四种常用模型,用于双指

算法题-双指针(最长的指定瑕疵度的元音子串(答案、解析))-爱代码爱编程

目录 题目 最长的指定瑕疵度的元音子串 题目描述 解答要求 答案 解析 核心思想 题目 注意要选好先判断左指针还是右指针可以节省不必要的操作。 最长的指定瑕疵度的元音子串 hash算法、双指针 题目描述 定义:开头和结尾都是元音字母(aeiouAEIOU)的字符串为元音字符串,其中混杂的非元音字母数量为瑕疵度。比如: “a”、“

AcWing算法基础课-双指针-爱代码爱编程

双指针算法 模板: for(int i=0,j=0;i<n;i++) { while(j<i && check(i,j)) j++; //具体问题逻辑 } 常见问题分类: (1):对于一个序列,用两个指针维护一段区间 (2):对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作 双指针算法核心:优化 两

双指针算法-爱代码爱编程

文章目录 双指针算法1.基本介绍2.模板3.例题总结 双指针算法 1.基本介绍 严格的来说,双指针只能说是是算法中的一种技巧。 双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。最常见的双指针算法有两种:一种是,在一个序列里边,用两个

寻路算法 --- A星寻路算法-爱代码爱编程

深度寻路算法应用场景  仅用于空旷地形,小游戏或者大游戏的某个小模块,点击地图,人物一步步试探 广度寻路算法应用场景  只适用于小地图,回合制的走格子游戏,上帝视角,在走之前已经把路都找出来了 A星寻路算法应用场景 应用场景广泛 RPG游戏:为什么小兵追着人物砍?怎么样知道人物在哪?怎么样给它自动规划路径?人物自动跑图,怎么实现? 通过A星算

简单分析双指针算法时间复杂度为什么是O(n)-爱代码爱编程

前言   很久没有更新了,这段时间还是以输入为主。今天复习双指针的时候,突然想明白了为什么双指针算法的时间复杂度是O(n)而不是O( n 2

开始学算法6===>哈希表进阶+双指针进阶(leetcode刷题!!!)_zhutouasam的博客-爱代码爱编程

哈希表进阶+双指针进阶(LeetCode刷题!!!) 跟着carl哥的第六天哈希表进阶先看第一道题再看第二道题 双指针进阶第一道题最后一道坚持一下!!!! 自我总结 跟着carl哥的第六天 今

2022大厂面试秘籍java岗:中间件+算法+http+线程+虚拟机+分布式_啊码的博客-爱代码爱编程

前言 很多朋友对面试不够了解,不知道如何准备,对面试环节的设置以及目的不够了解,因此成功率不高。通常情况下校招生面试的成功率低于1%,而社招的面试成功率也低于5%,所以对于候选人一定要知道设立面试的初衷以及每个环节的意义,

李宏毅:life long learning_bulibuli蛋的博客-爱代码爱编程

Life Long Learing 也是continual Learning,也是incremental learning 目录 Life-Long Learning  vs  Transfer Learning Evaluation Research Directions Selective Synaptic Plasticity——Regul

基础算法-爱代码爱编程

文章目录 一、排序1.快速排序2.归并排序 二、二分1、整数二分2、浮点数二分 三、高精度四种应用场景:①加法:②减法:③乘法:④除法: 四、前缀和1、一维2、二维 五、差分1.一维差分