3.无重复字符的最长子串

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

子串

的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

class Solution {
    public int lengthOfLongestSubstring(String s) {

        // 无重复字符的最长子串
        //思路：从头开始，找到不重复的字符，一旦找到重复的字符，则停止，一直向下进行。
        Map<Character,Integer> map = new HashMap<>();
        int index = 0;
        for(; index < s.length(); index++){
            if(!map.containsKey(s.charAt(index))){
                map.put(s.charAt(index),1);
            } else{
                break;
            }
        }
        //当前不含有重复字符的 最长 子串 的长度
        int currentMax = map.keySet().size();

        //从index开始
        for(; index < s.length(); index++){
            map.put(s.charAt(index),map.getOrDefault(s.charAt(index),0)+1);
            //先不去除第一个判断
            if(judgeHaveRepeat(map)){
                if(map.get(s.charAt(index-currentMax)) > 1){
                    map.put(s.charAt(index-currentMax),map.get(s.charAt(index-currentMax))-1);
                } else {
                    map.remove(s.charAt(index-currentMax));
                }
            } else {
                currentMax = Math.max(map.keySet().size(),currentMax);
            }
        }

        return currentMax;
    }

    private boolean judgeHaveRepeat(Map<Character,Integer> map){
        if(map == null || map.isEmpty()){
            return false;
        }

        for(Character charAt :map.keySet()){
            if(map.get(charAt) > 1){
                return true;
            }
        }
        return false;
    }
}

//滑动窗口解题模板：

//我希望这种滑动窗口的模板题，你们不要再写的五花八门了。这是最简单的模板，拿走不谢。 模板：

//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
	//当前考虑的元素
	while (l <= r && check()) {//区间[left,right]不符合题意
        //扩展左边界
    }
    //区间[left,right]符合题意，统计相关信息
}

优化后：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //滑动窗口,左指针
        int left = 0;
        Set<Character> set = new HashSet<Character>();

        //最大长度
        int max = 0;

        for(int i = 0 ;i < s.length(); i++){
            
            //如果发现重复，则左指针加一
            while(set.contains(s.charAt(i))){
                set.remove(s.charAt(left++));
            }

            set.add(s.charAt(i));
            max = Math.max(max,i - left + 1);
        }

        return max;
    }

}