题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

解题思路

首先从头开始遍历字符串，当发生重复时，不抛弃之前的成果，而是把重复位置的下一个字符当作新一轮次的起始字符，继续循环，如此往复。

解题代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        if (len <= 1)
            return len;
        
        
        // 用于记录重复的字符，判断字符是否重复时还需要判断是否在本轮查找中。
        Map<Character,Integer> map = new HashMap<>();
        // 记录已查找到的最大子串长度
        int max = -1;
        // 记录当前轮次查找到的最大子串长度
        int curMax = 0;
        // 记录上次发生重复的位置
        int next = -1;
        // 用于保存HashMap中查询的结果
        // HashMap的put方法是如果已经有key存在，则返回修改前对应的value，然后更新value。
        // 如果调用put方法时key不存在，则返回null。
        Integer index = null;
        
        // 循环便利字符串
        for (int i = 0; i < len; i++) {
            // 如果出现重复字符，并且重复字符的位置出现在这轮查找中， 则更新轮次，重新记录查找的开始范围和最大子串长度
            if ((index = map.put(s.charAt(i), i)) != null && index > next) {
                next = index;
                curMax = i - index - 1;
            }
            
            // 更改最大值
            curMax++;
            if (curMax > max) 
                max = curMax;
        }
        
        return max;
    }
}

题目来源

力扣第三题