双指针算法(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]]-- 

看这样一个例子

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