AcWing 799. 最长连续不重复子序列——算法基础课题解
原文中文，约2600字，阅读约需7分钟。
📝
内容提要
给定长度为n的整数序列，找出最长的不包含重复数的连续区间，并输出其长度。使用左右指针遍历数组，左指针表示窗口的左边界，右指针表示当前考虑的数组元素。如果右指针指向的元素重复，则左指针向右移动，直到重复元素的计数恢复为1或更少。最后输出最长连续区间的长度。
🎯
关键要点
-
题目要求找出最长的不包含重复数的连续区间，并输出其长度。
-
输入包括一个整数 n 和 n 个整数的序列。
-
输出为最长不包含重复数的连续区间的长度。
-
数据规模为 1≤n≤10^5。
-
使用左右指针遍历数组，左指针表示窗口的左边界，右指针表示当前考虑的数组元素。
-
如果右指针指向的元素重复，左指针向右移动，直到重复元素的计数恢复为1或更少。
-
最后输出最长连续区间的长度。
❓
延伸问答
如何找到最长的不包含重复数的连续区间？
使用左右指针遍历数组，左指针表示窗口的左边界，右指针表示当前考虑的元素。如果右指针指向的元素重复，左指针向右移动，直到重复元素的计数恢复为1或更少。
输入数据的格式是什么？
输入包括一个整数 n 和 n 个整数的序列，第一行是整数 n，第二行是 n 个整数。
这个算法的时间复杂度是多少？
算法的时间复杂度为 O(n)，因为每个元素最多被访问两次。
如何处理重复元素的情况？
当右指针指向的元素重复时，左指针向右移动，直到该元素的计数恢复为1或更少。
输出的结果是什么？
输出为最长不包含重复数的连续区间的长度。
这个问题的输入规模限制是什么？
数据规模为 1≤n≤10^5。
🏷️
