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

题目描述

思路及解法

由于题目要求求出字符串中最长的连续无重复字符的最长子串，所以利用这个特性我们可以比较容易的想到利用双指针中的滑动窗口技巧来解决，但在实际的求解中我们可以利用其它的一些数据结构的特性来帮助实现窗口的滑动，在本体中就利用set集合不能有重复的特性来实现：

1.形成窗口：定义指向字符串s中字符下标为0的“指针”q与p（形成窗口），定义int类性变量maxLen用于记录最长的连续子串，定义std::unordered_set set来用于接下来辅助动态维护窗口；
2.动态维护窗口：

2.1若当前字符不存在set中则将其添加到set中并且让q++；并判断当前“q - p > maxLen”是否成立；成立则更新maxLen的值
2.2若
当前字符存在于set中，则set除去p所指向的字符（set.erase(s.at§)）;并入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;
        }
        int p = 0;
        int q = 0;
        unordered_set<char> set;
        int maxLen = 0;
        while (q < n) {
            char c = s.at(q);
            if (set.find(c) == set.end()) {
                set.insert(c);
                q++;
                if (q - p > maxLen) {
                    maxLen = q - p;
                }
                continue;
            }
            while (set.find(c) != set.end()) {
                set.erase(s.at(p));
                p++;
            }
        }
        return maxLen;
    }
};