关联题目： 最长不含重复字符的子字符串

1.滑动窗口

①出现在窗口外，不管

②出现在窗口内

#include<bits/stdc++.h>

using namespace std;
int a[100010];

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

        vector<int> pos(100010,-1);  // pos存的是a[i] 对应的 下标
        int res = 0;

        // [j,i]维护一个滑动窗口
        for( int i=0,j=0; i<n; i++ )
        {
            // 出现在窗口内,更新左边界
            if( pos[a[i]]>=j ) j = pos[a[i]]+1;
            res = max(res,i-j+1);
            // pos保存的是上一次的最近的，会覆盖
            pos[a[i]] = i;
        }

        cout<<res;
        return 0;
}

2.DP思路

视频讲解

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;

int a[N];
int f[N];  // f[i]表示以a[i]结尾，不重复子串的最大长度

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

        vector<int> pos(100010,-1);  // pos存的是a[i] 对应的 下标
        f[0] = 1;
        pos[a[0]] = 0;

        for( int i=1; i<n; i++ )
        {
            if( pos[a[i]]==-1 ) f[i] = f[i-1]+1;
            else  
            {
                if( i-f[i-1] > pos[a[i]] ) f[i] = f[i-1]+1;  // 不在窗口内
                else f[i] = i - pos[a[i]];  // 在窗口内
            }
            // pos保存的是上一次的最近的，会覆盖
            pos[a[i]] = i;
        }

        int res = 0;
        for( int i=0; i<n; i++ ) 
        {
                res = max(res,f[i]);
                //cout<<f[i]<<' ';
        }
        cout<<res;
        return 0;
}