题目描述:
给定一个字符串 s
,请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"
,所以其长度为 3。
实现逻辑:
类似于伸手去一个不透光的箱子里掏带有颜色的小球,挨个将掏出的小球装进一个瓶子里,每往瓶子里装一个小球就更新一次临时最大值currentMax,当某次掏出的小球颜色在瓶子里已有,则拿一个新瓶子来装该小球,同时在Max和currentMax中选一个最大值更新Max,当箱子里已经没有小球时则表明遍历结束。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> charSet; // 用于存储当前窗口中的字符
int left = 0; // 滑动窗口的左边界
int maxLength = 0; // 记录最长子串的长度
// 遍历字符串
for (int right = 0; right < s.size(); ++right) {
// 如果当前字符已在窗口中,移动左边界缩小窗口
while (charSet.find(s[right]) != charSet.end()) {
charSet.erase(s[left]);
left++;
}
// 将当前字符加入窗口
charSet.insert(s[right]);
// 更新最大子串长度
maxLength = max(maxLength, right - left + 1);
}
return maxLength;
}
};
代码逻辑:
代码中,用瓶子的过程可以用集合unordered_set<char> charSet;来代替,集合中每个元素只会出现一次。
如何去判断新掏出的小球颜色(新的字母元素)是否已经在瓶子(集合)中出现,用迭代器find即可,拿一个新瓶子的过程可以用
while (charSet.find(s[right]) != charSet.end()) {
charSet.erase(s[left]);
left++;
}
实现,假设瓶子中已经有红蓝绿三个颜色,新的小球颜色为蓝色,通过while循环,让left指向绿色小球,因为从此刻开始,不重复的连续序列应该时蓝绿,而瓶子中此时只有绿色,所以在while循环后,还需要将新颜色的小球加入瓶子中。
而后不断地更新max: maxLength = max(maxLength, right - left + 1);