Leetcode Longest Substring Without Repeating Characters (cpp)

题目

解法1：sliding window

利用滑动窗口，使得窗口内始终不包含重复元素

• 顺序移动右边界，如果右边界所指元素已经在窗口出现，那么移动做指针知道右边界所指元素被移出窗口
• 现在窗口内已经不包含右边界所指元素，更新右边界所指元素的出现次数，并且更新最大长度
  需要注意这边有符号和空格，所以要注意其他符号的ASCII值

class Solution {
    
public:int lengthOfLongestSubstring(string s) {
    vector<int> seen(400,0);int l = 0;int max_len = 0;for (int r = 0;r<s.size();r++){
    while (seen[s[r]-'a'+200]){
    seen[s[l]-'a'+200] -= 1;l++;}seen[s[r]-'a'+200] += 1;max_len = max(max_len,r-l+1);}return max_len;}
};

解法2：

同样是利用滑动窗口的思想，这边用了一个小技巧。上面是记录某个字符出现的次数来保证滑动窗口内不包含重复元素，这边直接记录某个字符出现的位置，当重复字符在右边界出现时，我们找到上一次这个字符出现的位置，以这个位置的下一个位置作为左边界更新最大长度

class Solution {
    
public:int lengthOfLongestSubstring(string s) {
    vector<int> seen(400,-1);int l = 0;int max_len = 0;for (int r = 0;r<s.size();r++){
    if (seen[s[r]-'a'+200] != -1){
    l = max(l,seen[s[r]-'a'+200]+1);}max_len = max(max_len,r-l+1);seen[s[r]-'a'+200] = r;}return max_len;}
};