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

题目概述：给定一个字符串s，求该字符串中无重复字符的子串的最长长度
解题思路：用一个哈希表来记录每个字符最近出现的位置。指针i遍历s，并用另一个指针j从当前位置的下一个位置开始遍历，每次检查当前枚举的字符上一次出现的位置pos是否>=i，如果>=i，说明当前子串中出现重复字符，更新答案，指针i直接跳到该位置即pos处，哈希表清空，指针j继续从i的下一个位置开始遍历；如果pos<i，说明该字串中还没出现重复字符，长度加1，更新哈希表。
时间复杂度：\(O(n^2)\),竟然过了，数据挺水的
代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        //record the last position that appear
        Map<Character,Integer>last = new HashMap<>();
        int res = 0;
        for(int i = 0; i < s.length(); i ++){
            int len = 1;
            last.put(s.charAt(i),i);
            for(int j = i + 1; j < s.length(); j ++){
                int pos = last.getOrDefault(s.charAt(j),-1);
                if(pos >= i){
                    i = pos;
                    //last.put(s.charAt(j),j);
                    res = Math.max(res,len);
                    last.clear();
                    break;
                }else{
                    len++;
                    last.put(s.charAt(j),j);
                }
            }
            res = Math.max(res,len);
        }

        return res;
    }
}

正解：在上述暴力做法中，当遇到含重复字符的子串时。我们让指针i回到该字符上一次出现的位置，并且让j指针从该位置的下一个下一个位置开始枚举。但其实我们可以发现j指针又会重复枚举那段不包含重复字符的串，因此我们可以让j不向回走。i指针每次向右移动一个单位，j指针一直移动到其能到达的最右端(不出现重复字符)。类似一个滑动窗口，期间需要一个哈希表来维护出现的字符，j指针移动时向其中加入字符，i指针移动时，需要删除字符
时间复杂度：\(O(n)\)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character>set = new HashSet<>();
        int res = 0;
        int r = -1;

        for(int l = 0; l < n; l ++){
            if(l != 0){
                set.remove(s.charAt(l - 1));
            }

            while(r + 1 < n && !set.contains(s.charAt(r + 1))){
                r++;
                set.add(s.charAt(r));
            }

            res = Math.max(res,r - l + 1);
        }

        return res;
    }
}