题目描述

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

样例

5
1 2 2 3 5

3

算法

(双指针)

1. j ++要放在s[a[j]] --的后面
2. 哈希的思想
3. i - j + 1直接求出长度，一开始我还定义了一个变量，有些繁琐了
4. for()循环的形式的for(int i = 0, j = 0; i < n; i ++)，也就是一开始i和j是同一个起点的，然后i往后移动，当j~i这个区间出现了重复元素的时候，j再向靠近i的位置移动，但是j <= i，永远不会超过i，同时移动j的目的是将j指向的元素清除s[a[j]] --

时间复杂度

$O(n)$

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N], s[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];

    int res = 0;
    for(int i = 0, j = 0; i < n; i ++)
    {
        s[a[i]] ++;
        while(j <= i && s[a[i]] > 1)
        {
            s[a[j]] --;
            j ++;                     // **1
        }

        res = max(res, i - j + 1);    // **2
    }

    cout << res << endl;

    return 0;
}