无重复最长子串

LIZHAO LeetCode
阅读量 0 评论量 0

Leetcode:无重复最长子串

掌握程度:★ ☆ ☆

思路:使用滑动窗口原理

两个(left、right)游标同时指向数组的第一位,两层循环,分别用于移动left和right.

内层循环进入的条件时,右侧的游标小于字符串的长度,并且在窗口内没有重复的字符。

进入内层循环后,将字符添加到窗口中,并移动right游标。

当退出内层循环的时候,一定是right到达字符串的末端,或者窗口出现重复字符。

计算窗口的最大值,并移动左侧的游标,将left所指的元素移除窗口。

class Solution {
public:
    //滑动窗口
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> charset;
        //left和right同时指向第一个元素
        int left = 0, right = 0, res = 0;
        while (left < s.size()) {
            //右指针在字符串范围内,并且所指向的元素在子串中没有出现过,则向右移动指针
            while (right < s.size() && charset.count(s[right]) == 0) {
                charset.insert(s[right]);
                right++;
            }
            res = std::max(res, right - left);
            //出循环后一定是到达上限,或者存在相同的元素了。
            charset.erase(s[left]);
            ++left;
        }
        return res;
    }
};
喵~