1.核心思想

优化暴力解法算法复杂度O(n2)到O(n)

2.问题特征

(1)对于一个序列，用两个指针维护一段区间
(2)对于两个序列，维护某种次序，比如归并合并两个有序的序列

3. 分析流程

step1: 先用暴力算法给出求解方法
step2: 看i和j有没有某种单调关系（这里注意：维护一段序列，我们通常的做法是固定以i为一段区间的终点，前向搜索j到某个位置，之后i往后移动一个单位，看j是否只能往一个方向移动）

4. 代码模板

for(int i = 0, j = x; i < n; i++)
{
    // step1: j范围有效 & 设计某个性质，使的j具有某种单调性
    while(j < m && check(i, j)) jxx

    // step2：这道题目的具体逻辑

    // step3: 这里注意i，j的更新！！
}

题目描述举例

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

第一行包含整数n。

第二行包含n个整数（均在0~100000范围内），表示整数序列。
输出格式

共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。
数据范围

1≤n≤100000

样例

输入样例：

5
1 2 2 3 5

输出样例：

3

C 代码

#include<stdlib.h>
#include<stdio.h>
#include<math.h>

#define N 100010

int a[N];
int n;
int cnt[N];

int main(){
    //input
    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }

    int ans = 0;
    for(int i = 0, j = 0; i < n; i++){
        cnt[a[i]] += 1;
        while(j <= i && cnt[a[i]] > 1){
            cnt[a[j]] --;
            j++;
        }

        ans = fmax(ans, i - j + 1);
    }

    printf("%d", ans);

    return 0;
}