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: 哈希表，双指针，滑动窗口