题解 | #牛妹的项链#

题目关键信息：
1.数组a代表项链的每颗珠子，不同的数字代表不同颜色的珠子，而且这是个环形数组，首尾是相连的
2.求最长连续不重复子序列的长度
方法一：暴力
用list存储最长不重复子序列，因为是环形珠子，考虑首尾相连的情况，将珠子复制一份接到后面，因此循环从0到2n，每次取a[i%n],如果list中不存在此数字，则将数字加入列表，否则，为了保证珠子的连续性，从头部不断移除数字直到将重复数字移除，每次将珠子加入列表时维护最大值

图片说明

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int[] a) {
        // write code here
        //记录连续不重复颜色珠子的长度
        List<Integer>list=new LinkedList<Integer>();
        int max=0;
        //因为是环形珠子，考虑首尾相连的情况，将珠子复制接到后面
        for(int i=0;i<2*n;i++){
            //如果重复，则列表不断移除第一个珠子直到移除掉重复的珠子，
            while(list.contains(a[i%n])){
                list.remove(0);
            }//将珠子加入列表
            list.add(a[i%n]);
            max=Math.max(max,list.size());//维护珠子长度最大值
        }return max;
    }
}

复杂度：
时间复杂度：两层循环，最差达到 $图片说明$
空间复杂度：辅助列表大小不超过n， $O(n)$
方法二：动态规划
同样,考虑到首尾相连的情况，定义 $dp$ 数组的大小为 $2*n$ ， $dp[i]$ 表示以 $a[i]$ 结尾最长连续不重复子序列的长度, $dp[0]$ 初始化为1，
状态转移方程：

第i个元素与前面的元素出现重复： $dp[i]=dp[i-1]$
第i个元素与前面的元素未出现重复： $dp[i]=dp[i-1]+1$
利用set判断元素是否出现重复，如果第i个元素能够添加进set，说明未重复

图片说明

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int[] a) {
        // write code here
        int[]dp=new int[2*n];
        //dp[i]表示以a[i]结尾最长连续不重复子序列的长度
        dp[0]=1;
        Set<Integer>set=new HashSet<Integer>();
        set.add(a[0]);
        int max=dp[0];
        for(int i=1;i<2*n;i++){
            //如果第i个元素添加进set成功，说明前i个元素中没有重复元素
            if(set.add(a[i%n]))dp[i]=dp[i-1]+1;
            else dp[i]=dp[i-1];//有重复元素则继承上一个的子序列的长度
            max=Math.max(max,dp[i]);//取最大值
        }
        return max;

    }
}

复杂度：
时间复杂度：一层循环，并且HashSet是基于散列表实现的，add()方法的时间复杂度为 $O(1)$ ,因此总的时间复杂度为 $O(n)$
空间复杂度： $dp$ 数组的大小为 $2n$ ,空间复杂度为 $O(n)$
方法三：滑动窗口
设置左指针和右指针分别指向起点,当左指针和右指针都未指向末尾时，利用set判断元素是否出现重复，如果第i个元素能够添加进set，说明未重复，右指针右移，否则左指针右移，，每次子序列长度为 $r-l$ ,更新最大值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int[] a) {
        // write code here
        Set<Integer>set=new HashSet<>();
        int max=0;
        int l=0,r=0;
        //因为是环形珠子，考虑首尾相连的情况，将珠子复制接到后面
        while(l<2*n&&r<2*n){
            //如果添加到set成功,说明没有重复,右指针右移
            if(set.add(a[r%n])){
                r++;
            }//否则左指针左移
            else l++;
            max=Math.max(max,r-l);//右指针减去左指针的长度，维护最大值
        }return max;
    }
}

复杂度：
时间复杂度：一层循环，并且HashSet是基于散列表实现的，add()方法的时间复杂度为 $O(1)$ ,因此总的时间复杂度为 $O(n)$
空间复杂度：set大小不超过n， $O(n)$