题解：AcWing 799 最长连续不重复子序列

【题目来源】

AcWing：799. 最长连续不重复子序列 - AcWing题库

【题目描述】

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

【输入】

第一行包含整数 \(n\)。

第二行包含 \(n\) 个整数（均在 \(0\sim 10^5\) 范围内），表示整数序列。

【输出】

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

【输入样例】

5
1 2 2 3 5

【输出样例】

3

【解题思路】

【算法标签】

《AcWing 799 最长连续不重复子序列》 #双指针#

【代码详解】

#include <bits/stdc++.h>
using namespace std;const int N = 100010;  // 定义数组最大长度int n;                // 数组长度
int a[N];             // 存储原始数组
int s[N];             // 哈希表，记录每个数字出现的次数int main()
{// 输入数组长度cin >> n;// 输入数组元素for (int i = 0; i < n; i++){cin >> a[i];}int res = 0;  // 记录最长无重复子数组长度// 双指针算法：i是右指针，j是左指针for (int i = 0, j = 0; i < n; i++){s[a[i]]++;  // 记录当前数字出现次数// 如果当前数字出现次数超过1次，移动左指针jwhile (s[a[i]] > 1){s[a[j]]--;  // 减少左指针指向数字的计数j++;        // 左指针右移}// 更新最大长度res = max(res, i - j + 1);}// 输出最长无重复子数组长度cout << res << endl;return 0;
}

【运行结果】

5
1 2 2 3 5
3