题解 | #牛妹的项链#

题意整理

牛妹有一条由n个珠子组成的项链，每个珠子都有自己的颜色。
现在牛妹要截取一段尽可能长的珠子，但是截下的这一段不能有相同颜色的珠子。

方法一（暴力统计）

1.解题思路

简要分析：由于项链总共有n颗珠子，我们可以枚举所有的起始位置，然后从每个起始位置开始，最多截取n个珠子，每一个起始位置（记为start）对应的终点位置最多为start+n，如果超过n就对n取余。固定起始位置之后，就开始截取，可以用一个set集合存储之前截取过的珠子，一旦遇到颜色重复的珠子，直接终止循环，此时的set容量即为当前起点对应的最大珠子数。

首先定义结果变量，用于记录最终结果。
以每一个位置为起始点，往后截取。如果不在set，说明可以截取；如果在，说明已经是最大长度，记录下来。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int[] a) {
        //初始化结果变量
        int res=0;
        //以每一个位置为起始点，往后截取
        for(int start=0;start<n;start++){
            Set<Integer> set=new HashSet<>();
            //最多截取n个
            for(int i=start;i<start+n;i++){
                //如果不在set，说明可以截取
                if(!set.contains(a[i%n])){
                    set.add(a[i%n]);
                }
                //如果在，直接终止循环
                else{
                    break;
                }
            }
            //记录每个起点往后截取的最长一段珠子长度
            res=Math.max(res,set.size());
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：最坏情况下，两层循环体总共执行 $n^2$ 次，所以时间复杂度是 $O(n^2)$ 。
空间复杂度：最坏情况下，需要额外n个大小为n的哈希表，所以空间复杂度是 $O(n^2)$ 。

方法二（滑动窗口+哈希表）

1.解题思路

简要分析：仔细琢磨这一句话，牛妹不喜欢同一个颜色出现两次，如果把珠子比作字符串中的字符串，颜色相同看作遇到了相同的字符，那么只要把珠子数组延长一倍，问题就转化为在一个字符串中寻找最长不含重复字符的子字符串。

初始化map，用于记录之前颜色相同珠子所在位置的下一位。
如果当前位置对应颜色的珠子曾经出现在map，则将滑动窗口起点移动到之前记录位置的后一位。
每一轮循环，都统计最长的珠子长度。

动图展示：
图片说明

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int[] a) {
        //初始化map
        Map<Integer,Integer> map=new HashMap<>();

        //res记录最长的珠子长度，start记录珠子起点
        int res=0,start=0;
        for(int i=0;i<2*n;i++){
            //如果之前出现在map，则将滑动窗口起点移动到之前记录位置的后一位
            if(map.containsKey(a[i%n])){
                start=Math.max(start,map.get(a[i%n]));
            }
            map.put(a[i%n],i+1);
            //每次都统计最长的珠子长度
            res=Math.max(res,i-start+1);
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：循环最多执行 $2*n$ 次，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外大小为n的哈希表，所以空间复杂度是 $O(n)$ 。