Problem: 3. 无重复字符的最长子串

题目描述

思路及解法

1.川建一个set集合存储最长的无重复的字符；
2.创建双指针p、q，每次当q指针指向的字符不在set集合中时将其添加到set集合中让q指针后移，并且更新无重复字符串的最大长度，当q指向的字符在set集合中时，抹去p指针指向的字符

复杂度

时间复杂度:

$O(n)$;其中$n$为字符串$s$的长度

空间复杂度:

$O(n)$

Code

class Solution {
public:
    /**
     * Two Pointer
     *
     * @param s Given string
     * @return int
     */
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        unordered_set<char> set;
        int p = 0;
        int q = 0;
        int maxLen = 0;
        while (q < n) {
            if (!set.count(s[q])) {
                set.insert(s[q]);
                q++;
                maxLen > q - p ? maxLen : q - p;
                continue;
            }
            while (set.count(s[q])) {
                set.erase(s[p]);
                p++;
            }
        }
        return maxLen;
    }
};