leetcode3. 无重复字符的最长子串 [滑动窗口]

题目

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

示例 1:

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

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路

设置两个指针left、right。固定left，向右移动right。设置set集合存储滑动窗口中的字符元素。

情况①，当s[right] 没有在set集合中找到时，就将它插入到set集合；

情况②，若在set集合中找到，则删除left指针指向的元素，直到set中没有与 s[right]相同的元素。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 10.17 19:00
        set<char> st;
        int len = s.size();
        int left = 0, right = 0;
        int res = 0;	// 最长子串长度
        while (left < len) {
            if (st.find(s[right]) == st.end()) {
                st.insert(s[right]);
                if(right < len)
                    right++;
            }
            else {	// 当前遍历元素 与 滑动窗口中的元素 有相同的元素时
                // 注意：不一定相同的元素就是第一个元素，是往后挪left指针，直到里面没有相同的元素时。
                char c = s[right];
                int length = right - left;
                if (length > res)	res = length;
                while (st.find(s[right]) != st.end()) {
                    st.erase(s[left++]);
                }
                // left++;
            }
        }
        return res;
 
    }
};

运行结果