Leetcode 3. Longest Substring Without Repeating Characters / 四六文摘

Given a string s, find the length of the longest substring without repeating characters.

题解：
初步想法是用一个map数组储存现在遍历的字符串里的字符，初定义maxlen=0，nowlen=0,然后从字符串最先开始遍历，每次遍历一个字符便开始判断是否map里它对应的值是0吗？若是，则令其为1（代表现在字符串里有它），nowlen ;若否，则判断nowlen和maxmlen的大小并作出变化，nowlen再清零从这个字符重新开始遍历直到遍历结束。
在实现的过程中，我先后发现了这些问题：

我没有考虑到全部都是不重复的情况
我之前的思路是遇到重复的就全部清零，再从这个字符继续（因为之前觉得没必要从当前遍历的字符串的第二个字符开始，觉得遍历后的结点绝对比之前的短，现在想想是完全错误的）
因此针对这两种情况我做了一些修改，通过了，但是代码效率似乎不高。
代码：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()==0||s.length()==1) return s.length();
        int maxlen=0,nowlen=0,index=0,hindex=0;
        unordered_map<char,int> m;
        while(index<s.length()){
            if(m[s[index]]==0){  //index号字符和之前的未重复
                m[s[index]]=1;
                nowlen  ;
                index  ;
            }
            else{
                if(nowlen>maxlen) maxlen=nowlen;
                nowlen=0;
                m.clear();
                hindex  ;
                index=hindex;
            }
        }
        if(nowlen>maxlen) maxlen=nowlen;
        return maxlen;
    }
};

在很多OJ上是不会提供给你具体的测试样例的，所以在写之前要想完全全部的情况，为了应对未来未知情况。

if(nowlen>maxlen) maxlen=nowlen;
这一句可以用max（）函数来代替。

去看了看其他大神的代码并理解了一下思想：
我发现了一个核心点：下一次开始的子字符串头从哪开始？
其他的代码很妙的一点是，直接把字符能换算成整数这一点利用上，存在一个数组内（这一点我是用map实现的），而这里设计特别巧妙，通过本次子序列往后遍历，找到第一个与本次序列停止的字符重复的字符，并从这个字符的下一个字符开始下一次的子序列.

于是我再次做了修改，将此思想运用到我的代码中：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()==0||s.length()==1) return s.length();
        int maxlen=0,nowlen=0,index=0,hindex=0;
        unordered_map<char,int> m;
        while(index<s.length()){
            if(m[s[index]]==0){  //index号字符和之前的未重复
                m[s[index]]=1;
                nowlen  ;
            }
            else{
                maxlen=max(maxlen,nowlen);
                while(s[hindex]!=s[index]){
                    m[s[hindex]]=0;
                    hindex  ;
                }
                hindex  ;
                nowlen=index-hindex 1;
            }
            index  ;
        }
        maxlen=max(maxlen,nowlen);
        return maxlen;
    }
};

果然快了很多。来源：https://www.icode9.com/content-4-897701.html

Leetcode 3. Longest Substring Without Repeating Characters

相关推荐