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:00set<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;}
};

运行结果