双指针算法

算法思路

双指针算法思路
    1.确定指针含义
    2.发现单调性
    确定指针含义:首先确定一个从左向右遍历的指针i作为区间右端点,区间左端点j的含义(与i的关联):
与i距离最近且[j,i]无冗余元素的位置.也就是说[1,i]中的元素在[j,i]都能找到,且没有元素是没必要重复的.
比如112223,对于最后一个位置的i,j在第二个位置,如果j再向右一步,区间少了1,向左一步,区间多余一个1.
    单调性:可以证明随着i的增加,j一定不减小.
        反证法:假设[j,i],对于i' = i + 1,其对应的j'<j,因为我们定义j对于i是没有冗余的,所以[1,i]中的元素
    在[i,j]都存在,那么[j',i]的元素[j,i]也都存在,[j',i']的元素在[j,i']也都存在,所以j'存在冗余,与定义不符。

    那么这个没有冗余如何实现呢?j位置有冗余也就是j对应元素在j右侧存在,也就是j可以被替代.我们用一个cnt数组
表示每个字符出现次数,当cnt[j]>1时说明j的右侧有相同字符,j冗余,可以继续向右前进.
(类似于AcWing 799. 最长连续不重复子序列)

时间复杂度

O(n)

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 2e5 + 10;

char s[N];
int cnt[3];

int main()
{
    int T;
    scanf("%d",&T);
    while( T-- )
    {
        scanf("%s",s);
        int n = strlen(s), res = n + 1;
        memset(cnt,0,sizeof cnt);
        for( int i = 0, j = 0; i < n; i++ )
        {
            cnt[s[i]-'1']++;//'s' -> [0,2]
            while( cnt[s[j]-'1'] > 1 )
            {
                cnt[s[j]-'1']--;
                j++;
            }
            if( cnt[0] && cnt[1] && cnt[2] )
                res = min( res, i - j + 1 );
        }
        if( res == n + 1 )  res = 0;
        printf("%d\n",res);
    }
    return 0;
}