题解 | #最长无重复子数组#
最长无重复子数组
http://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4
直接用for循环遍历,在遍历过程中用map存储每一个(arr[i],i),每一次遍历都需要查看map中是能根据arr[i]找到i,如果能,说明已经重复,用list保存长度,同时取出i,下一次需要从i+1开始,因为两个相同的数字之间可能存在多个不重复的数字,这段数字需要加到后面的计算中。最后直接对list排序,取出最大值即可。代码如下:
import java.util.*; public class Solution { /** * 运行时间:237ms *.超过73.50% 用Java提交的代码 *.占用内存:26968KB *.超过98.16%用Java提交的代码 * @param arr int整型一维数组 the array * @return int整型 */ public int maxLength (int[] arr) { // write code here int flag = 0; Map<Integer, Integer> map = new HashMap<Integer,Integer>(); List<Integer> list = new ArrayList<Integer>(); for(int i=0; i<arr.length; i++){ if(map.get(arr[i]) == null){ flag++; map.put(arr[i],i); }else{ list.add(flag); flag = 0; i=map.get(arr[i]); map.clear(); } } list.add(flag); Collections.sort(list); return list.get(list.size()-1); } }