牛妹的项链

有一个项链共有n个珠子,每个珠子都有一个颜色,这n珠子构建成一个环,牛妹想要一段最长的珠子其中同一个颜色不出现两次。

案例
输入：4,[3,1,1,2]
返回值：3
说明：
牛妹可以选择在第3个珠子的左边和右边各切一刀，截取第4个，第1个和第2个珠子连起来的连续珠子。

方法一 暴力

遍历a中的每一个珠子i，每次从第i个珠子开始往后遍历记录最长不重复颜色的珠子长度。

class Solution {
public:
    int solve(int n, vector<int>& a) {
        // write code here
        int ans = 0;
        for(int i = 0; i < n; i ++){
            unordered_map<int, bool> vis;
            for(int j = i; j < n * 2; j ++){ //从第i个开始统计后面最长能到多少
                if(vis[a[j % n]]){ //如果存在则更新
                    ans = max(ans, (j - 1) - i + 1);
                    break;
                }
                vis[a[j % n]] = 1;
            }
        }
        return ans;
    }
};

时间复杂度: 最多会是一整个项链是合法的
空间复杂度: map最多会记录一整个项链的长度

方法二 尺取

定义两个变量l和r表示l到r这一段为合法的项链段，考虑两种情况，一如果把当前遍历到的第r位加入项链中没有出现重复的颜色，那么将答案更新，如果出现重复颜色则将l的位置向前移一位并去除l位的颜色直到没有重复颜色出现为止。

class Solution {
public:
    unordered_map<int, int> mp; //标记颜色是否出现
    int solve(int n, vector<int>& a) {
        // write code here
        for(int i = 0; i < n; i ++) a.push_back(a[i]); // 奖a数组翻倍
        n *= 2;
        int l = 0, r = 0, ans = 0;
        for(r = 0; r < n; r ++){
            mp[a[r]] ++;
            while(l < r && mp[a[r]] > 1) mp[a[l ++]] --; //当前的珠子时如果有重复取则将l不断加到没有重复的情况
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

时间复杂度: 在项链全部颜色为相同时最多会遍历2遍项链
空间复杂度: map中最多会标记整个项链的颜色