每天坚持做算法题，熟悉基本的套路，巩固语言基础，总结经验记下所学所想。

题目

输入一个长度为n（n≤106）的序列A，找到一个尽量长的连续子序列AL～AR，使得该序
列中没有相同的元素。

思路1

HINT

假设序列元素从0开始编号，所求连续子序列的左端点为L，右端点为R。首先考虑起
点L=0的情况。可以从R=0开始不断增加R，相当于把所求序列的右端点往右延伸。当无法延
伸（即A[R+1]在子序列A[L～R]中出现过）时，只需增大L，并且继续延伸R。既然当前
的A[L～R]是可行解，L增大之后必然还是可行解，所以不必减少R，继续增大即可。
不难发现这个算法是正确的，不过真正有意思的是算法的时间复杂度。暂时先不考
虑“判断是否可以延伸”这个部分，每次要么把R加1，要么把L加1，而L和R最多从0增加到n-
1，所以指针增加的次数是O(n)的。
最后考虑“判断是否可以延伸”这个部分。比较容易想到的方法是用一个STL的set，保
存A[L～R]中元素的集合，当R增大时判断A[R+1]是否在set中出现，而R加1时把A[R+1]插入到
set中，L+1时把A[L]从set中删除。因为set的插入删除和查找都是O(logn)的，所以这个算法的
时间复杂度为O(nlogn)。代码如下：

代码

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;

const int maxn = 1000000 + 5;

int A[maxn];

int main( ) {
    int T, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%d", &A[i]);

        set<int> s;

        int L=0, R=0, ans = 0;
        while(R<n){

            while(R<n&&!s.count(A[R])){
                s.insert(A[R])
                ++R;
            }
            ans = max(ans, R - L);
            ++L;
            s.erase(A[L])
        }
        cout<<ans;
    }

}

思路2

HINT

另一个方法是用一个map求出last[i]，即下标i的“上一个相同元素的下标”。例如，输入
序列为3 2 4 1 3 2 3，当前区间是[1,3]（即元素2, 4, 1），是否可以延伸呢？下一个数是
A[5]=3，它的“上一个相同位置”是下标0（A[0]=3），不在区间中，因此可以延伸。map的所
有操作都是O(logn)的，但后面所有操作的时间复杂度均为O(1)，总时间复杂度也
是O(nlogn)。

代码

#include<map>
using namespace std;
const int maxn = 1000000 + 5;
int A[maxn], last[maxn];
map<int, int> cur;

int main( ) {
    int T, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        cur.clear( );
        for(int i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            if(!cur.count(A[i])) last[i] = -1;
            else last[i] = cur[A[i]];
            cur[A[i]] = i;
        }

        int L = 0, R = 0, ans = 0;
        while(R<n){
            while(R<n&&last[R]<L) ++R;
            ans = max(ans, R - L);
            ++L;
            // L = last[R]+1;
        }
        cout<<ans;
    }
}

int Solution::lengthOfLongestSubstring(string s) {

    vector<int> dict(256, -1);
    // map<char, int> mp;
    int maxLen = 0, start = -1;
    for (int i = 0; i != s.length(); i++) {
        if (dict[s[i]] > start)
            start = dict[s[i]];
        //if(mp.count(s[i]))
        //    if(mp[s[i]] > start)
        //        start = mp[s[i]];
        dict[s[i]] = i;
        maxLen = max(maxLen, i - start);
    }
    return maxLen;
}