相信大家都是看完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]]--
看这样一个例子
如果各位还有更好的理解思路和我的思路有问题都可以告诉我更正
