【12. 最大连续不重复子序列】

双指针算法的俩种情况

#include <iostream>
#include <string.h>
#include <cstdio>

using namespace std;

int main()
{
    char str [1000];
   //scanf("%s", str);
   
   
     fgets(str,sizeof(str), stdin);
     int n = strlen(str);
    for (int i = 0; i < n; i ++)
    {
        int j = i;
        while (j < n && str[j] != ' ') j ++;
        
        // 这道题的具体逻辑
        for (int k = i; k < j; k ++) cout << str[k];
        cout << endl;
        
        i = j;
    }
    return 0;
}

运行结果:
输入：
abc def cde
输出：
abc
def
cde

最大连续不重复子序列

• 额外开辟一个数组S[N]，动态的记录一下，元素出现了多少次，相当于i每次往后移动一格，就往S[N]中加入一个元素，如果j往前移动一格，相当于出现重复数字，在从S[N]中删除掉该元素。
• 最后可以动态的统计出，该数组中有多少个数

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

题目

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

输入格式

第一行包含整数 n。

第二行包含 n个整数（均在 0∼100000范围内），表示整数序列。

输出格式

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

数据范围

1 ≤ n ≤ 100000

输入样例：

5
1 2 2 3 5

输出样例：

3

代码

#include<iostream>
using namespace std;

const int N = 100010;
int n;
int a[N],s[N];
int main()
{

   cin >> n;
   for (int i = 0; i < n; i ++)  cin >> a[i];
   
   int res = 0;
   for (int i = 0, j = 0; i < n; i ++)
   {
       s[a[i]] ++;
       while (s[a[i]] > 1)
       {
           s[a[j]] --;
           j ++;
       }
       res = max(res, i - j + 1);
   }
   cout << res << endl;
   return 0;
}