题目描述

题目大意&链接

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

输入输出样例：
输入：

5
1 2 2 3 5

输出：

3

详情：ac_799最长连续不重复子序列

解题思路

这题采用双指针的思想，具体：

采用 map 哈希表存储数列中个元素出现的次数，i 指针往后移动，当 mp[a[i]] > 1 时，表示前面有重复元素，此时将 j 指针后移一位并 mp[a[j]]– ：
map<int, int> mp;
...
mp[a[i]]++;
while(mp[a[i]] > 1)
{
mp[a[j]]--;
j++;
}
res 记录最长连续不重复子序列：
res = max(res, i - j + 1);

完整代码

#include<iostream>
#include<map>

using namespace std;

const int N = 1e6 + 10;

int n;
int a[N], s[N];
map<int, int> mp;

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    int res = 0;
    for(int i = 0, j = 0; i < n; i++)
    {
        // s[a[i]]++; 用数组或者哈希表来存储都可以
        mp[a[i]]++;
        while(mp[a[i]] > 1)
        {
            // s[a[j]]--;
            mp[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    printf("%d", res);
    return 0;
}

时间和空间复杂度

时间复杂度：O(nlogn) map 基于红黑树实现，单次操作时间为 O(logn)，数组存储的话就是 O(n);
空间复杂度：O(n)