题目

• 3. 无重复字符的最长子串 - 力扣（LeetCode）

简述

• 给到我们一个字符串, 要求返回其最长无重复子串的长度, 注意是最长子串, 而不是子序列

分析

• 在没学到哈希表之前, 我苦想于该如何判断重复并停止加入集合中, 本想直接用StringBuilder进行拼接第一个字符, 然后将StringBuilder转换成String对象, 继续对新的字符串遍历判断下一个原字符串中的字符是否重复于StringBuilder中的字符, 但是这样做只能返回其无重复的子序列.
• 在有了哈希表之后, 判断重复就简单了许多.
• 如果我们有两个指针, 一个在用来记录无重复子串的开始, 另一个指针不断向右移动, 直到遇到有重复的元素为止, 然后我们将该子串的长度记录, 再将左指针右移一次, 此时两指针内的子串一定是无重复的, 再判断右指针是否该右移, 但注意左指针左移后, 需要将前一个字符在哈希表中删除

代码如下

public int lengthOfLongestSubstring(String s) {
                //先创建一个HashSet
                HashSet<Character> hs = new HashSet<>();
                //max用于后续记录子串的长度
                int max = 0;
                //用作右指针, 初始值为-1是因为我们的右指针所指的字符是已经存入集合中的
                //我们需要判断右指针下一个字符即(end+1)是否重复于集合所存的字符
                //所以需要初始值为-1, 因为我们要将字符串中0索引的字符添加到集合中
                int end = -1;
                //遍历字符串, i就可以作为左指针, 我们在for循环中将右指针的操作全部完成
                //即已经找到了一个无重复子串, 并且记录了子串的长度
                //做完这些, 就可以将左指针左移
                for (int i = 0; i < s.length(); i++) {
                    //由于每次移动左指针都需要将上一个字符删除
                    //所以只要左指针不为0, 则说明已经需要将上一个字符删除了
                    if (i != 0) hs.remove(s.charAt(i - 1));
                    //为了确保右指针做完所有事情, 所以用while循环
                    //循环条件是右指针的下一个字符不超过字符串的长度, 并且下一个字符没有和集合中的字符重复
                    while (end + 1 < s.length() && !hs.contains(s.charAt(end + 1))) {
                        //符合条件则将下一个字符添加到集合中
                        hs.add(s.charAt(end + 1));
                        //不断移动右指针, 直到条件不符合
                        end++;
                    }
                    //记录集合中的子串长度, 然后将其于下一个子串的长度对比, 取最大值
                    max = Math.max(max, end + 1 - i);
                }
                return max;
            }