描述
给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。
数据范围：0<=val<=1000000
数据数量范围：0<=n<=100000
要求：时间复杂度O（nlogn),空间复杂度为O（n）
示例1
输入：
[2,3,4,5]
返回值：
4
说明：
[2,3,4,5]是最长子数组
示例2
输入：
[2,2,3,4,3]
返回值：
3
说明：
[2,3,4]是最长子数组
这一题解法有很多，解法一。我们可以找一个队列，不停的把元素介入到队列中。如果有相同的元素就把队列中首元素移除。这样队列中就没有重复元素了。然后记录下队列元素存储的最大值，最后返回此值即可。下面请看代码：
Java版：
public int maxLength (int[] arr) {// write code hereint result=0;int length=arr.length;Queue<Integer> queue=new LinkedList<>();for(int c:arr){while(queue.contains(c)){//如果有重复元素则移除队首元素，直到不重复为止queue.poll();}queue.add(c);//将元素添加到队尾result=Math.max(result,queue.size());}return result;}
这个方法就不写C++版的了，因为C++的队列中没有检测是否包含某个元素的功能。
方法二：用set代替队列，设置两个指针，一个left，一个right，如果有重复的就把left所指的元素移除。（left相当于队首，right相当于队尾）
Java版：
public static int maxLength(int []arr){int result=0;int left=0;int length=arr.length;int right=0;Set<Integer> set=new HashSet<>();while(right<length){while(set.contains(arr[right]))set.remove(arr[left++]);set.add(arr[right++]);result=Integer.max(result,set.size());}return result;}
C++版：使用c++来写我们可以简单一点，开一个100000个数据的数组，数组下标就是对应的值，如果数据被加进去就把数组数据设置为1，没有加就设置为0。用空间换取时间，下面请看代码：
int maxLength(vector<int> arr){int left=0;int right=0;int Max=0;//记录不重复元素最大数量int length=arr.size();vector<int>v(100000);//开一个100000个元素的数组，且值初始化为0while(right<length){//如果v[arr[right]]!=0，说明v中包含这个数据，//那就删除走指针所指的数据，且做指针享有移动一位while(v[arr[right]]!=0)v[arr[left++]]=0;//v中添加右指针所指的数据，且右指针向右移动一位v[arr[right++]]=1;Max=max(Max,right-left);}return Max;}
转载请注明：XAMPP中文组官网 » 较难题:最长无重复数组