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

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

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。
提示
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
解题思路：
从左往右扫描，每次找出i位置字符的最长子串和i-1位置的最长子串对比，保留最长子串的长度 max 直到扫描结束
需要的参照物，上一个最长子串的起始位置li, i 位置字符的上一次出现位置pi, 试想 当 li < pi 或 li == pi, 那么i位置字符的最长子串起始位置应该就是 li = pi + 1 ；相反 li > pi 此时i位置字符的最长子串起始位置应该不变

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
     //空判断
     if(s==null) return 0;
     char[] list = s.toCharArray();
     //担心给一个空串 ""
     if(list.length == 0) return 0;
     //定义一个变量来保存每一个字符上一次出现的位置 
     Map <Character, Integer> prevIndex = new HashMap<>();
     //把第0个字符先保存下来 因为我们需要依据 i 和 i-1 位置字符的相对关系来操作，所以i要从1下标位开始扫描
     prevIndex.put(list[0],0);
     int li = 0;//以i-1位置字符结尾的最长不重复字符串的开始索引(最左索引) 为 0 - 0
     int max = 1;//最长子串的初始值为1
     for(int i = 1; i < list.length; i++) {
        //1. 取出i位置字符上一次出现的位置
        Integer pi = prevIndex.get(list[i]);
        //2. 对比li 和 pi 的大小，得到i位置字符的最长子串的起始位置 li
        if(pi != null && li <= pi) { 
                //如果i位置字符从来没有出现过 pi的值是null, 没出现过那 li 就是i位置字符最长子串的起始位置 跟 i-1 是一样的
            li  = pi + 1;
        }
        //3. 存储i位置字符出现的位置
        prevIndex.put(list[i],i);
        //4. 求出最长不重复子串的长度
        max = Math.max(max,i - li + 1);

     }

    return max;

    }
}

优化方案：

思路：因为s 由英文字母、数字、符号和空格组成所以这些字符就是单字节字符，每一个字符都占1位，那么这就是ASCII咯，ASCII共128个字符，所以保存每一个字符上一次出现的位置 就可以不用哈希表，改用数组

class Solution {
    public int lengthOfLongestSubstring(String s) {
     //空判断
     if(s==null) return 0;
     char[] list = s.toCharArray();
     //担心给一个空串 ""
     if(list.length == 0) return 0;
     //定义一个变量来保存每一个字符上一次出现的位置 
     int[] prevIndex = new int[128];
     for(int i = 0; i < prevIndex.length; i++) {
         prevIndex[i] = -1;
     }
     //把第0个字符先保存下来 因为我们需要依据 i 和 i-1 位置字符的相对关系来操作，所以i要从1下标位开始扫描
     prevIndex[list[0]] = 0;
     int li = 0;//以i-1位置字符结尾的最长不重复字符串的开始索引(最左索引) 为 0 - 0
     int max = 1;//最长子串的最先值就是1
     for(int i = 1; i < list.length; i++) {
        //1. 取出i位置字符上一次出现的位置
        int pi = prevIndex[list[i]];
        //2. 对比li 和 pi 的大小，得到i位置字符的最长子串的起始位置 li
        if(li <= pi) { 
            li  = pi + 1;
        }
        //3. 存储i位置字符出现的位置
        prevIndex[list[i]] = i;
        //4. 求出最长不重复子串的长度
        max = Math.max(max,i - li + 1);

     }

    return max;

    }
}