讨论/题目交流/无重复字符的最长子串的结果解析有问题/
无重复字符的最长子串的结果解析有问题

题目要求给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
这个题目给的一个输入是

"\" \""

,我的代码在本地idea运行结果是2,但在这个问题结果反馈页给出的运行结果是0,
我实际走了一遍代码流程结果也是2,页面给的运行结果有问题。
另外,我觉得这个输入的结果应该是2,即一个引号加一个空格长度为2,但是答案给的是1,这个答案是否也有问题

代码如下:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //1.首先将字符串转为一个字符数组
        //2.使用传统的for循环遍历时间复杂度会很高,使用set集合无法满足要求,这里使用map,键存字符值,值存字符数组下标;
        //3.定义两个int low,high,low表示无重复子串的最低位数组下标,high表示最高位数组下标,初始值都为0;
        //4.定义一个int len表示无重复子串最长长度,初始为0;
        //5.遍历字符数组,i表示遍历次数,即数组第i位;
        //6.存字符值和它的下标存到map,每次存时判断map中是否有该字符,有则证明到了无重复子串的最长位置,将high赋值为i;
        //7.high-low得到的值与len比较,大于len则赋值给len;
        //8.将i的值变为map中存的重复字符的下标+1,即从不重复子串将要重复的字符的下一位开始遍历,同时将low的值变为i;
        //9.遍历剩下的数组,遇到重复的取出map里的下标,
                //下标小于low,改变map里该字符的value为当前i;
                //判断下标大于low,则证明该重复字符位于当前不重复子串,将high赋值为i,转到第七步;
        //10.直到i遍历到数组最后,返回len
        
        
        char[]  chars = s.toCharArray();
        int low = 0; 
        int high = 0;
        int maxLen = 0;
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        for(int i=0; i<chars.length; i++){
            if(!map.containsKey(chars[i])){
                map.put(chars[i],i);
            }else{
                if(map.get(chars[i])>=low){
                    high = i;
                    if(high-low > maxLen)
                        maxLen = high-low;
                    i = map.get(chars[i]);
                    low = i+1;
                }else{
                    map.put(chars[i],i);
                }
            }
        }
        return maxLen;
    }
}

idea运行结果.png

结果有问题.png

展开讨论

经过大佬的解答,改了一上午,发现一堆问题,最后终于解决了,从执行时间131ms优化到11ms,很开心,附代码:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        /**思想:使用low和high标识无重复字符串的最低位和最高位,使用map遍历字符数组存字符,当遇到一个重复字符,通过low和high计算无重复子串的长度,从子串中重复字符的下一个开始重新构建无重复子           *串,同时改变low的值,将map中存的该重复字符的下标更改为当前循环层,比如abcbdfc,当循环到第二个b时重复,则从第三位的c开始重新构建子串,同时改变map里b的value为第二个b的下标,循环的位           *置不变,因为c到第二个b是第一个无重复子串的一部分,必然无重复,直接从第二个b继续遍历即可。
        */
        //1.首先将字符串转为一个字符数组
        //2.使用传统的for循环遍历时间复杂度会很高,使用set集合无法满足要求,这里使用map,键存字符值,值存字符数组下标;
        //3.定义两个int low,high,low表示无重复子串的最低位数组下标,high表示最高位数组下标,初始值都为0;
        //4.定义一个int len表示无重复子串最长长度,初始为0;
        //5.遍历字符数组,i表示遍历次数,即数组第i位;
        //6.存字符值和它的下标存到map,每次存时判断map中是否有该字符,有则证明到了无重复子串的最长位置,将high赋值为i;
        //7.high-low得到的值与len比较,大于len则赋值给len;
        //8.将low的值变为map中存的重复字符的下标+1,即从不重复子串将要重复的字符的下一位开始重新选择不重复子串,i的值不变;
        //9.改变map里该重复字符的value为当前i;
        //10.从i继续遍历,遇到重复的取出map里的下标,
                //判断下标大于low,则证明该重复字符位于当前不重复子串,将high赋值为i,转到第七步;
        //11.直到i遍历到数组最后,循环结束
        //12.考虑到这种方式不能判断给的字符串就是无重复字符的情况,如a,ab,abc,所以在循环外执行:high赋值为i,high-low得到的值与len比较,大于len则赋值给len;
        //13.返回len
        
        
        char[]  chars = s.toCharArray();
        int low = 0; 
        int high = 0;
        int maxLen = 0;
        int i = 0;
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        for(i=0; i<chars.length; i++){
            if(!map.containsKey(chars[i])){
                map.put(chars[i],i);
            }
            else{
                if(map.get(chars[i])>=low){
                    high = i;
                    if(high-low > maxLen)
                        maxLen = high-low;
                    low = map.get(chars[i])+1;
                }
                map.put(chars[i],i);
                
            }
        }
        high = i;
        if(high-low > maxLen)
            maxLen = high-low;
        return maxLen;
    }
}
展开全部 2 讨论