滑动窗口-3. 无重复字符的最长子串-leetcode

桃扇骨 2023-09-25 17:08 18阅读 0赞

[3. 无重复字符的最长子串 - 力扣（Leetcode）][3. _ - _Leetcode]

## 题目 ##

![9a44e991a73b44048f42d0e07458131c.png][]

## 原理 ##

以示例一中的字符串 abcabcbb\\texttt\{abcabcbb\}abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：

![406d301acef444f18f545c7da9e1b783.png][]

![212335efbd1840c1a911cc3e47ad8112.png][]

![661a76a6733b4bb8bf7b20032de0810d.png][]

## 代码，代码里的注释也是原理的理解，更容易通俗 ##

class Solution {
        public int lengthOfLongestSubstring(String s) {
            //哈希集合
            Set<Character> occ = new HashSet<>();
            int n = s.length();
            //记录字符串的长度
            int right = -1;
            //右指针，初始值为-1，相当于在字符串的左边界的左侧，这时候，还没有开始移动
            /*为什么右指针要用-1初始化？
             * 因为右指针要先检查下一位是否与哈希集合中的某个字符重复
             * 所以要先从-1的位置开始检查0那个位置上的字符*/
            int len = 0;//用来记录子串的长度
            for (int left = 0; left < n; left++) {//左指针left，从0开始
                if (left != 0) {
                    /*左指针每向右移动一位就移除哈希集合中的一位字符，左指针用for循环移动
                     * 左指针先向右移动一位，再移除一位元素
                     * 所以，当left在m位置的时候，移除的是m-1位置的上元素*/
                    occ.remove(s.charAt(left-1));
                }
                /*就是以左指针所在的字符的位置作为子串的起止位置
                 * 然后以右指针作为子串的终止位置
                 * 一位意味地往后检查字符
                 * 如果右指针的下一位字符在两个指针之间没有重复过，就将这个字符加入子串，然后右指针右移一位，继续检查下一位
                 * 如果右指针的下一位字符在两个指针之间重复过，就执行for循环条件中的left++，然后left指针移除一位
                 * left指针也是先移位再移除
                 * 在这过程中，记录下子串拥有过的最大的长度并返回*/
                while(right+1<n&&!occ.contains(s.charAt(right+1))){
                    occ.add(s.charAt(right+1));
                    right++;
                }
                len=Math.max(len,right-left+1);
            }
            return len;
        }
    }

[3. _ - _Leetcode]: https://leetcode.cn/problems/longest-substring-without-repeating-characters/submissions/414583521/?envType=study-plan&id=suan-fa-ru-men&plan=algorithms&plan_progress=xhp164ue
[9a44e991a73b44048f42d0e07458131c.png]: https://img-blog.csdnimg.cn/9a44e991a73b44048f42d0e07458131c.png
[406d301acef444f18f545c7da9e1b783.png]: https://img-blog.csdnimg.cn/406d301acef444f18f545c7da9e1b783.png
[212335efbd1840c1a911cc3e47ad8112.png]: https://img-blog.csdnimg.cn/212335efbd1840c1a911cc3e47ad8112.png
[661a76a6733b4bb8bf7b20032de0810d.png]: https://img-blog.csdnimg.cn/661a76a6733b4bb8bf7b20032de0810d.png