HashMap

找到字符串的最长无重复字符子串

http://www.nowcoder.com/questionTerminal/b56799ebfd684fb394bd315e89324fb4

public int maxLength (int[] arr) {
    HashMap<Integer,Integer> map = new HashMap<>();
    int max = 1;
    for(int start = 0, end = 0; end<arr.length ; end++){
        if(map.containsKey(arr[end])){
            //重复了
            start = Math.max(start, map.get(arr[end])+1);
            //注意：这里一定要取最大的start，不然就错误了
            //为什么？ 因为重复数字的索引很可能比start小
        }
        max = Math.max(max , end-start+1);
        map.put(arr[end],end);
    }
    return max;
}

全部评论

推荐最新楼层

hh~~~1

中南大学 Java

哎自己怎么就写不出来呢

4 回复分享

发布于 2020-09-09 18:12

改个名真nm的难

合肥工业大学 Java

HashMap不好的地方就在于不知道字符的顺序不好排除之前序列的元素，明明XYYX形的第一个X都不用考虑的（发现Y重复时就已经连同第一个Y一起被remove掉了），却还得start = Math.max(start, map.get(arr[end])+1);这样去判断，但HashMap O(1)时间的查找确实比LinkedList O(n)的查找香。

1 回复分享

发布于 2020-10-05 20:52

Hijet

Harvard University C++

我理解的意思是找到以arr[end]结尾的最长子串，然后max保持最大长度，当某个数在之前出现过，这个时候就把子串的起点start往后推一个，但是有一种情况，比如1，2，3，4，3，5，1。到第二个3时，以后的子串起点start为4，到第二个1时，如果不取最大的start，按start = map.get(arr[end])+1 算出起点start为2，显然以起点start=2，结尾end=1的子串234351有重复的，因此start要取最大的

16 回复分享

发布于 2020-11-24 15:56

老衲帅过

河北科技大学测试开发

public int maxLength (int[] arr) { // write code here int max = 1; HashMap<integer> intMap = new HashMap(); for(int i = 0; i < arr.length; ) { if(intMap.containsKey(arr[i])) { max = max > intMap.size() ? max : intMap.size(); i = intMap.get(arr[i]) + 1; intMap.clear(); } else { intMap.put(arr[i], i); i++; max = max > intMap.size() ? max : intMap.size(); } } return max; } 我觉得这样写，对我自己来说，比较好理解</integer>

点赞回复分享

发布于 2021-05-15 08:38

monty1

东南大学 Java

你好，你在更新left指针的时候，你既然已经保存了重复的位置，为什么不直接用map里保存的下标更新呢？直接left = map.get(arr[end]) + 1

点赞回复分享

发布于 2021-04-20 17:27

MIDOUO

运城学院测试开发

妙啊

点赞回复分享

发布于 2021-04-17 20:37