题解 | #牛妹的项链#

题目描述
牛妹收到了一个项链，这个项链一共有n个珠子，每个珠子都有一个颜色 ai 。这n个珠子构成了一个环。

不知为何，牛妹想从项链上截下一段连续的珠子，但是牛妹不喜欢同一个颜色出现两次，所以截下来的这一段珠子中没有相同的颜色。现在牛妹想知道她可以截下的最长的一段珠子为多长？

第i个珠子与第i+1个珠子和第i−1个珠子相邻。(i>1且i<n)
特别的，与第1个珠子相邻的珠子为第2个，第n个珠子。
与第n个珠子相邻的珠子为第n-1个，第1个珠子。

方法一：暴力求解

求解思路
对于本题目的求解，我们可以枚举所有起始位置，然后从每个起始位置开始，最多截取n个珠子，然后通过数组进行记录，最后保存最大珠子数量。按照上述思路，即可求出本题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int solve (int n, int[] a) {
        int myres=0; // 存储结果
        for(int start=0;start<n;start++)
        {
            Set<Integer> set=new HashSet<>(); // 保存最大值
            for(int i=start;i<start+n;i++)
            {   //往后选n个珠子
                if(!set.contains(a[i%n]))
                {
                    set.add(a[i%n]);
                }
                else
                {
                    break;
                }
            }
            myres=Math.max(myres,set.size()); // 更新结果
        }
        return myres; // 返回结果
    }
}

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用set[n],因此空间复杂度为 $O(N)$

方法二：优化思想求解

求解思路
我们想到字符串求解重复子串的思路，因此我们将珠子延长一倍，然后从两倍珠子中去寻找即可。按照上述思路同样可以得到本问题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int solve (int n, int[] a)
    {
        Map<Integer,Integer> mymap=new HashMap<>();
        int myres=0,start=0;
        for(int i=0;i<2*n;i++)
        {   //延长珠子的数量
            if(mymap.containsKey(a[i%n]))
            {
                start=Math.max(start,mymap.get(a[i%n])); // 更新位置
            }
            mymap.put(a[i%n],i+1);
            myres=Math.max(myres,i-start+1); // 更新结果
        }
        return myres; // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用mymap[n],因此空间复杂度为 $O(N)$