最长无重复子串

问题描述：

给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。

示例1

输入：[2,3,4,5]

返回值：4

示例2

输入：[2,2,3,4,3]

返回值：3

备注:

1≤n≤10 ^5

直接暴力求解时间复杂度为o^2超时。

所以采用HashMap来求解

思路：将数组中的元素值和下标存入HashMap，在存入之前做一个判断，判断HashMap中是否存在当前元素，如果不存在，put()，如果存在，取出HashMap中元素个数，并清空HashMap，并将待输入元素下标赋值为当前元素的下标。详情请看代码及注释。

上代码：

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     *给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。
     */
    public int maxLength (int[] arr) {
        int max=1;//初始化子串长度，最短为1
        int sum=0;//sum用于统计遍历数组时，无子串长度
        Map <Integer,Integer> map = new HashMap<>();//定义map
        for(int index=0,temp;index<arr.length;index++){
            temp = arr[index];
            if(!map.containsKey(temp)){//如果map中不存在temp元素，则将该元素即下标放入map
                map.put(temp,index);
                sum++;//统计个数+1
            }
            else{//如果存在相同元素，则判断谁是最大的，并重新计数
                max = (int)Math.max(sum,max);
                sum=0;
                index = map.get(temp);//将重复元素的下标作为下一次遍历的开始。
                map.clear();清空map容器
            }
        }
        return (int)Math.max(sum,max);
    }
}