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

本文介绍: 该题我们可以采用滑动窗口的方法来解决，对于子数组，字串的题都经常用到滑动窗口的解决方法题目的要求是：1.要获得最长子串的长度 2.子串中不含有重复字符我们首先看到题目后可以想到的暴力解法就是，去获取字符串中所有的子串，筛选出不含有重复字符的字串，获取其中最长子串的长度，而滑动窗口方法就是在这基础上进行优化我们以题目给出的示例 1 来进行说明，输入: s = “abc abc b b“，一般遇到输入为字符串的题，通常都需要把字符串转换为字符数组，

代码：

//采用滑动窗口来进行解决
class Solution {
    public int lengthOfLongestSubstring(String s) {
        //字符串由英文字母、数字、符号和空格组成，通过对应的 ASCLL 码作为下标在数组中记录出现的次数
        //判断字符在字串中是否重复出现
        int[] ascll=new int[128];
        int maxLength=0;
        int length=s.length();
        int left=0;
        int right=0;
        char[] numsS=s.toCharArray();

        while (right&lt;length){
            //将 right 指针指向的字符添加到要讨论的子串中
            ascll[numsS[right]]++;
            //判断字串中是否有重复字符
            while (ascll[numsS[right]]&gt;1){
                //有重复字符
                //将 left 指针指向的字符从要讨论的字串中去除，再将 left 指针向右移动
                ascll[numsS[left++]]--;

            }
            //没有重复字符
            //把当前讨论的字串的长度与 maxLength 中记录的长度进行比较，记录大的值
            maxLength=Math.max(right-left+1,maxLength);
            right++;
        }

        return maxLength;
    }
}

题解：

该题我们可以采用滑动窗口的方法来解决，对于子数组，字串的题都经常用到滑动窗口的解决方法

题目的要求是：1.要获得最长子串的长度 2.子串中不含有重复字符

我们首先看到题目后可以想到的暴力解法就是，去获取字符串中所有的子串，筛选出不含有重复字符的字串，获取其中最长子串的长度，而滑动窗口方法就是在这基础上进行优化

我们以题目给出的示例 1 来进行说明，输入: s = “abc ab cb b“，一般遇到输入为字符串的题，通常都需要把字符串转换为字符数组，方便操作

1.我们用 L 指针和 R 指针来遍历字符串，获取字符串的子串（L 和 R 指针之间的字符便是我们当前要讨论的子串），让 L 指针和 R 指针指向 0 下标，此时我们要讨论的子串就是 a,a 里面没有重复的字符，所以我们可以记录该子串的长度，问题来了，我们如何判断当前子串有没有重复的字符呢？我们可以定义一个数组 a scll ，a scll 数组的下标代表字符的 ASCLL 码，数组中的值就代表 ASCLL 码对应的字符在子串中的个数，所以当 R 指针指向 a 时，就将 ascll 数组中，a字符的个数加1，拼接到子串中的字符就是 R 指针指向的字符，即使出现重复，也只会是刚刚拼接的字符重复，所以我们只需要判断刚刚拼接的字符的个数是否大于1，就知道当前讨论的子串中是否出现重复字符，此时 a 字符在 asc ll 数组中记录的个数为1，所以该子串不含有重复字符

a b c a b c b b

2.加长讨论的子串长度，R 指针向右移动,将 R 指针指向的 b 字符添加到要讨论的子串中，即将 b 字符在 asc ll 数组中的记录数加1，此时 b 字符在 asc ll 数组中的记录数为 1 ，所以该子串 ab 不含有重复字符，于是更新最大子串的长度（取当前子串长度和之前记录的最大长度较大的值）

a b c a b c b b

3.进行重复的操作，当 R 指针指向当前位置后，将 a 字符在 asc ll 数组中的记录数加1，此时 a 字符在 asc ll 数组中的记录数为 2，所以当前讨论的子串 ab ca 中含有重复字符，代表以当前 L 指针指向的字符为首位的字符串讨论完毕，将 L 指针向右移动，讨论以下一个字符为首位的字符串

a b c a b c b b

4.讨论以下一个字符为首位的字符串时涉及到一个问题，R 指针需要回到 L 指针所在的位置进行讨论吗？答案是不需要，因为 R 指针之前的数据已经证明是不含有重复字符的子串了，所以即使 R 指针回到 L 指针所在的位置，R 指针也会遍历到当前位置，所以我们直接讨论当前的 bca 子串中是否有重复字符即可，当 L 指针向右移动后，a 字符就不在要讨论的子串中了，在 ascll 数组中的记录数就减1，此时 a 字符在 ascll 数组中的记录数为 1，所以当前讨论的子串 bca 中不含有重复字符，于是更新最大子串的长度（取当前子串长度和之前记录的最大长度较大的值）