思路

• 用双指针i j维护一段区间， s[n]动态维护该区间每个数出现的次数

• i 一往无前， j后勤保障， 保证该区间每个数出现次数都为1

• 注意关键字 连续 不重复

双指针模板

• 单调性

• 减少枚举次数

• 可以减少枚举次数是满足某种性质，得找到这种性质；

for(i = 0, j = 0; i < n; i++)
{
    while(j < i && check(i, j)) j++

    // 每道题的具体逻辑
}
// 应用了某些性质(如单调性），将o(n2)的算法优化的o(n)，减少枚举次数

c++ 代码

时间复杂度 O(2n)
空间复杂度 O(n)

#include <iostream>

using namespace std;

const int N = 1e5 + 10; 

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]] ++; //维护 i j 区间内的数字出现次数
        while( s[a[i]] > 1) // 新加入一个重复了，那么肯定就是重复的就是新加入的
        {
            s[a[j]] --;
            j++;
        }

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

    cout << res << endl;
    return 0;
}

拓展

• 当数字很大时，数组开不了，可以用哈希表来做
• 无重复字符的的最长子串