题目描述：

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，请你找出最长的不包含重复元素的连续子数组，并输出它的长度。

例如，序列中的子数组 $a[l], a[l+1], \dots, a[r]$ 满足以下条件：对于任意 $i, j$（$i \neq j$），都有 $a_i \neq a_j$。

请编写程序来求解这个问题。

输入

• 第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示序列的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示整数序列。

输出

输出一个整数，表示最长不包含重复元素的连续子数组的长度。

样例输入 1：

7
1 2 3 1 2 3 4

样例输出 1：

4

样例输入 2：

5
1 1 1 1 1

样例输出 2：

1

提示

• 在样例输入 1 中，最长不包含重复元素的子数组是 $[1, 2, 3, 4]$，其长度为 4。
• 在样例输入 2 中，所有的元素都相同，因此最长的不包含重复元素的子数组长度为 1。

双指针3：最长连续不重复子序列

题解

题面描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，请你找出最长的不包含重复元素的连续子数组，并输出它的长度。

思路

我们可以使用滑动窗口（双指针）来高效解决这个问题。具体步骤如下：

1. 初始化：

   • 使用两个指针 left 和 right，都初始化为序列的起始位置$0$。
   • 使用一个哈希集合 seen 来记录当前窗口内出现的元素。
   • 使用一个变量 maxLength 来记录当前找到的最长子数组长度，初始值为$0$。

2. 滑动窗口遍历：

   • 遍历序列中的每个元素，right 指针从左到右移动。
   • 对于当前元素 a[right]：
     • 检查重复： 如果 a[right] 已经存在于 seen 集合中，说明当前窗口内有重复元素，需要通过移动 left 指针来缩小窗口，直到移除重复的元素。

     while a[right] in seen:
         seen.remove(a[left])
         left += 1
     

     Copy
     • 更新窗口： 将当前元素 a[right] 添加到 seen 集合中。
     • 更新最长长度： 计算当前窗口的长度 right - left + 1，如果大于 maxLength，则更新 maxLength。

     seen.add(a[right])
     maxLength = max(maxLength, right - left + 1)
     

     Copy

3. 最终结果：

   • 遍历完整个序列后，maxLength 即为所求的最长不包含重复元素的连续子数组的长度。

Python 代码实现

def longest_unique_subarray_length(a):
    seen = set()  # 用于记录当前窗口中的元素
    left = 0  # 左指针
    max_length = 0  # 最长不重复子数组的长度

    # 遍历数组
    for right in range(len(a)):
        # 如果当前元素在窗口中已经存在，收缩窗口
        while a[right] in seen:
            seen.remove(a[left])
            left += 1

        # 加入当前元素
        seen.add(a[right])
        
        # 更新最大长度
        max_length = max(max_length, right - left + 1)

    return max_length

# 主函数，读取输入
if __name__ == '__main__':
    n = int(input())  # 读取序列长度
    a = list(map(int, input().split()))  # 读取整数序列

    print(longest_unique_subarray_length(a))

以样例输入 1为例：

7
1 2 3 1 2 3 4

解释

• 初始时，left = 0，right = 0，seen = {}，max_length = 0。
• 逐步移动 right 指针：
  1. right = 0，元素为1，加入 seen，seen = {1}，max_length = 1。
  2. right = 1，元素为2，加入 seen，seen = {1, 2}，max_length = 2。
  3. right = 2，元素为3，加入 seen，seen = {1, 2, 3}，max_length = 3。
  4. right = 3，元素为1，已存在于 seen，移动 left 到1，移除元素1，加入新的1，seen = {2, 3, 1}，max_length保持为3。
  5. right = 4，元素为2，已存在于 seen，移动 left 到2，移除元素2，加入新的2，seen = {3, 1, 2}，max_length保持为3。
  6. right = 5，元素为3，已存在于 seen，移动 left 到3，移除元素3，加入新的3，seen = {1, 2, 3}，max_length保持为3。
  7. right = 6，元素为4，加入 seen，seen = {1, 2, 3, 4}，max_length更新为4。

最终，最长不包含重复元素的连续子数组为 [1, 2, 3, 4]，其长度为4。