双指针

双指针

八月 01, 2021

双指针算法

核心：将暴力做法优化到O(n)

1
2
3
4
5
6
//朴素做法O(n^2)
for(int i=0;i<n;i++){
    for(int j=0;j<=i;j++){
        if(check(j,i)) 					res=max(res,j-i+1);
    }
}
1
2
3
4
5
//双指针算法O(n)
for(int i=0,j=0;i<n;i++){
    while(j<=i&&check(j,i)) j++;
    res=max(res,j-i+1);
}

1 2 2 3 5

len 1 2 1 2 3
i 1 1 1 3 3 3
j 1 2 3 3 4 5

1
2
3
4
5
6
7
8
int i=1,j=1;
for(int i=1;i<=n;i++){
    s[a[i]]++;
    while(s[a[i]]>1){
        s[a[j++]]--;
    }
    ans=max(ans,i-j+1);
}