双指针算法(acwing)疑难讲解

简介: 双指针算法(acwing)疑难讲解

相信大家都是看完y总的课来看博客解惑的我会在这里分享一些我理解的细节

回顾一下题目

直接上代码

#include<iostream>
using namespace std;
const int N = 1e5+10;
int n;
//s[N]来存贮从j 到  i的这个区间内的数字出现的次数(这里的j到i是没有重复数字的区间)
//j是一直往右走的那么它之前经过的数字也就没用了,s[]数组中也就没必要存储他们的出现次数了
//如果还存着他们的次数的话还可能影响下面操作的进行
//这也是为什么要s[a[j]]--的具体原因
int a[N],s[N];
int main(){
    cin>>n;
    int res = 0;
    for (int i = 0;i < n;i++)   scanf("%d",&a[i]);
    for (int i = 0,j = 0;i < n;i++){
        //s[a[i]]这样存储可以存下来相同数字的数量  因为数字相同的时候s[]数组的下标相同
        //所以当a[]数组中的出现相同的数字的时候在s[]中都是同一个位置
        s[a[i]]++;
        while(j <= i && s[a[i]] > 1){  //其中j<=i可有可无
            s[a[j]]--;
            j++;
        }
        res = max(res,i - j + 1);
    }
    cout<<res;
    return 0;
}

1.

先看看        为什么 j 是单调的(只能往右走)

因为j和i这个区间内一定是最长的不重复区间所以j只要往左移动就会矛盾导致重复(不懂来看一个例子)

123445678

不难看出当 i 指向第二个4的时候(及重复的时候) j 就会移动当移动到和 无重复 数字的时候停止

所以j的位置前一个位一定会在j - i这个范围内有一个数字重复

2.

为什么j <= i可有可无,因为只有在区间内出现重复元素的时候j才会移动当j = i 的时候只有一个数组,绝对无重复,所以在j = i的时候一定会停止,最多达到j = i

3.

这两个步骤怎么理解   s[a[j]]--  ;  j++;

为什么要 s[a[j]]--

看这样一个例子

如果各位还有更好的理解思路和我的思路有问题都可以告诉我更正

目录
相关文章
|
19天前
|
算法 关系型数据库 MySQL
大厂算法指南:优选算法 ——双指针篇(下)
大厂算法指南:优选算法 ——双指针篇(下)
23 0
|
23天前
|
算法 容器
算法思想总结:双指针算法
算法思想总结:双指针算法
|
1月前
|
存储 算法 容器
【优选算法】—— 双指针问题
【优选算法】—— 双指针问题
【优选算法】—— 双指针问题
|
1月前
|
算法
我对双指针算法认知
我对双指针算法认知
|
2月前
|
算法 测试技术 C++
【双指针】【C++算法】1537. 最大得分
【双指针】【C++算法】1537. 最大得分
|
2月前
|
算法
【算法优选】双指针专题——叁
【算法优选】双指针专题——叁
|
2月前
|
算法 容器
【算法优选】双指针专题——贰
【算法优选】双指针专题——贰
|
2月前
|
算法
【算法优选】双指针专题——壹
【算法优选】双指针专题——壹
|
2月前
|
人工智能 算法 BI
*算法基础:双指针算法
*算法基础:双指针算法
35 1
*算法基础:双指针算法
|
2月前
|
算法
双指针算法(二)
双指针算法(二)
双指针算法(二)