最长无重复子串

问题描述：
给定一个数组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);
    }
}

最后

以上就是等待星月为你收集整理的最长无重复子串（Java版）最长无重复子串的全部内容，希望文章能够帮你解决最长无重复子串（Java版）最长无重复子串所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。