美文网首页
longest-substring-without-repeat

longest-substring-without-repeat

作者: DaiMorph | 来源:发表于2019-07-21 22:52 被阅读0次

    "滑动窗口"
    比方说 abcabccc 当你右边扫描到abca的时候你得把第一个a删掉得到bca,
    然后"窗口"继续向右滑动,每当加到一个新char的时候,左边检查有无重复的char,
    然后如果没有重复的就正常添加,
    有重复的话就左边扔掉一部分(从最左到重复char这段扔掉),在这个过程中记录最大窗口长度

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            vector<int>f(256,-1);
            int pre=-1,res=0;
            for(int i=0;i<s.length();i++)
            {
                pre=max(pre,f[s[i]]);
                res=max(res,i-pre);
                f[s[i]]=i;
            }
            return res;
        }
    };
    

    相关文章

      网友评论

          本文标题:longest-substring-without-repeat

          本文链接:https://www.haomeiwen.com/subject/fqlblctx.html