LC 3、无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的【最长字串】的长度。

示例：

输入: s = "abcabcbb"

输出: 3 

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

双指针+哈希表

定义两个指针start 和 end 表示当前处理的字串的头部和尾部，同时end指针不断向后移动，如果当前end指针指向的字符不再hash表中，将当前字符插入到hash表中，同时定义全局变量number，记录当前字串的最大长度。如果指针指向的字符在hash表中，start指针向前进位，end指针也向前进位。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> hash;
        int n = 0;
        for(int left = 0, right = 0; right < s.size();){
            while(hash.find(s[right]) != hash.end()){
                hash.erase(hash.find(s[left]));
                left++;
            }
            hash.emplace(s[right]);
            right++;
            n = max(n, right - left);
            
        }
        return n;
    }
};

我们需要注意的是，我们要首先需要确保当前需要遍历的字串中没有重复字母的出现，所以上述代码中的for循环便是起到这个作用

• 时间复杂度：虽然有两层循环，但每个字符在哈希表中最多只会被插入和删除一次，复杂度为 O(n)
• 空间复杂度：使用了哈希表进行字符记录，复杂度为 O(n)

Label: 哈希表，双指针，滑动窗口