双指针

zhouzhoubukuku · 2022-12-25 17:04:19 · 个人记录

题目最长连续不重复子序列

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

是区间，就有两个下标，于是可以用上双指针，然后再根据题意，不包含重复的数字的连续区间，于是便可以得到下面这个N方的做法

include<bits/stdc++.h>

int a[100005]; int b[100005]; //用b数组记录有没有重复数字

int main(){//无问题 int n; scanf("%d",&n); for(int i = 1; i <= n; i++){ scanf("%d",&a[i]); }

int maxn = 0; 
for(int i = 1; i <= n; i++){
    for(int j = i; j <= n; j++){
        b[a[j]]++; 
        if(b[a[j]] >= 2){
            break;
        }
        if(maxn < j - i + 1){
            maxn = j - i + 1;
        } 
    }
    for(int j = 0; j <= 100000; j++){
        b[j] = 0;
    }
}
printf("%d",maxn); 

}

然后，我们发现，在已经求过出现重复的时候不必再求，降到了n