滑动窗口

题目大意

给定一个长度为 的序列，求最长的连续子序列，使得子序列中所有元素互不相同。

解题思路

本题要求最长的不含重复元素的连续子序列，可以使用滑动窗口（双指针） 结合哈希表高效解决：

1. 滑动窗口：维护一个窗口 ，保证窗口内元素唯一。
2. 哈希表：记录每个元素最后出现的位置，用于快速判断重复和移动左指针。
3. 移动规则：
   • 右指针 逐个遍历序列。
   • 若当前元素 在哈希表中存在且其位置在窗口内（即 ），则将左指针 移动到该元素上一次出现位置的下一位。
   • 更新哈希表中 的位置为 。
   • 实时更新最大窗口长度 。

算法步骤

1. 读入测试数据组数 。
2. 对每组数据：
   • 读入序列长度 和序列 。
   • 初始化哈希表 last_occurrence（记录元素最后位置）、左指针 、最大长度 。
   • 遍历右指针 从 到 ：
     • 若 在哈希表中存在且其位置 ，更新 为该位置 。
     • 更新哈希表中 的位置为 。
     • 更新 。
   • 输出 。

复杂度分析

• 时间复杂度： 每组数据。每个元素被右指针访问一次，哈希表操作均摊 。
• 空间复杂度：。哈希表最坏存储所有不同元素。

代码实现

#include <cstdio>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<long long> arr(n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &arr[i]);
        }

        unordered_map<long long, int> last_occurrence;
        int left = 0, max_len = 0;
        for (int right = 0; right < n; right++) {
            long long snow = arr[right];
            auto it = last_occurrence.find(snow);
            // 若元素存在且在当前窗口内
            if (it != last_occurrence.end() && it->second >= left) {
                left = it->second + 1; // 移动左指针
            }
            last_occurrence[snow] = right; // 更新位置
            int current_len = right - left + 1;
            if (current_len > max_len) {
                max_len = current_len;
            }
        }
        printf("%d\n", max_len);
    }
    return 0;
}