美文网首页LeetCode题解及面试
【LeetCode】3. Longest Substring W

【LeetCode】3. Longest Substring W

作者: LeetPub | 来源:发表于2019-12-06 13:59 被阅读0次

    题意

    给定一个字符串,找出没有重复字符的最长子串;

    解答

    一般这种重复字符串、重复数字都优先考虑滑动窗口(使用左右边界两个指针实现。
    对于滑动窗口简单说明:(l是左边界,r是右边界)

    • 滑动窗口初始位置l=r=0;
    • 滑动窗口动态变化的,大小为r-l+1;
    • 滑动窗口l <= r;
    • 滑动窗口左右边界都向右滑动;

    针对找出没有重复字符的最长子串这种问题,最根本是找到最大的滑动窗口,且最大的滑动窗口中没有重复的字符,遵循的原则是如果即将进入滑动窗口右边界字符已经存在滑动窗口中,为了保证无重复字符串,则滑动窗口左边界要向右移动到已经存在字符的下一个位置,这样才能使将要进入的字符进入滑动窗口

    针对字符串pwwkew为例:

    • 初始状态,滑动窗口左右边界都指向0,l->0, r->0

    • 判断右边界p是否已经存在滑动窗口hash表中,不存在则加入hash表;

    • 滑动窗口右指针向右移动,r->1,判断右边界w是否已经存在滑动窗口hash表中,不存在则加入hash表;

    • 滑动窗口右指针向右移动,r->2,判断右边界w是否已经存在滑动窗口hash表中,hash表中已经存在,则左边界为hash表中已经存在字符的位置+1,即l=max(l, pos[s[r]+1])(注意:左边界不能左移),然后再更新已经存在字符的位置pos[s[r]]=r

    • 滑动窗口右指针向右移动,r->3,判断右边界k是否已经存在滑动窗口hash表中,不存在则加入hash表;

    • 滑动窗口右指针向右移动,r->4,判断右边界e是否已经存在滑动窗口hash表中,不存在则加入hash表;

    • 滑动窗口右指针向右移动,r->5,判断右边界w是否已经存在滑动窗口hash表中,hash表中已经存在,则左边界为hash表中已经存在字符的位置+1,即l=max(l, pos[s[r]+1])(注意:左边界不能左移),然后再更新已经存在字符的位置pos[s[r]]=r

    • 每次迭代选取最大的滑动窗口大小r-l+1;

    代码

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int res = 0;
            unordered_map<char, int> pos;
            for(int l = 0, r = 0; r < s.length(); ++ r) {
                if (pos.count(s[r])){
                    l = max(l, pos[s[r]]+1);
                }
                pos[s[r]] = r;
                res = max(res, r-l+1);
            }
            return res;
        }
    };
    
    

    相关文章

      网友评论

        本文标题:【LeetCode】3. Longest Substring W

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