AcWing 799. 最长连续不重复子序列——算法基础课题解
原文中文，约2600字，阅读约需7分钟。
📝
内容提要
给定长度为n的整数序列，找出最长的不包含重复数的连续区间，并输出其长度。使用左右指针遍历数组，左指针表示窗口的左边界，右指针表示当前考虑的数组元素。如果右指针指向的元素重复，则左指针向右移动，直到重复元素的计数恢复为1或更少。最后输出最长连续区间的长度。
🔎
延伸解读
双指针算法的核心机制
文章通过左右指针维护一个滑动窗口，右指针遍历数组，左指针在遇到重复元素时向右移动，直到窗口内无重复。这种设计保证了每个元素最多被左右指针各访问一次，因此时间复杂度为O(n)，适合处理n≤10^5的数据规模。
计数数组与哈希表的选择
代码示例中，C++使用固定大小的计数数组count，而Go版本提供了map和数组两种实现。由于题目中元素范围在0∼10^5，使用数组更高效；若元素范围未知或更大，则map更灵活。读者可根据实际数据范围选择合适的数据结构。
边界条件与循环终止
在移动左指针时，循环条件为l < r && count[arr[r]] > 1，确保左指针不会超过右指针，且重复计数降至1。这避免了数组越界，并保证窗口始终有效。最终结果通过max函数更新，记录遍历过程中的最大窗口长度。
❓
Q&A
如何找到最长的不包含重复数的连续区间？
使用左右指针遍历数组，左指针表示窗口的左边界，右指针表示当前考虑的元素。如果右指针指向的元素重复，左指针向右移动，直到重复元素的计数恢复为1或更少。
输入数据的格式是什么？
输入包括一个整数 n 和 n 个整数的序列，第一行是整数 n，第二行是 n 个整数。
这个算法的时间复杂度是多少？
算法的时间复杂度为 O(n)，因为每个元素最多被访问两次。
如何处理重复元素的情况？
当右指针指向的元素重复时，左指针向右移动，直到该元素的计数恢复为1或更少。
输出的结果是什么？
输出为最长不包含重复数的连续区间的长度。
这个问题的输入规模限制是什么？
数据规模为 1≤n≤10^5。
🏷️
