Leetcode 3.题目如下:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
实例:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
给你一个字符串S,寻找一个子串T,保证T里面的字符都是唯一的。
那么我们该如何思考这个问题呢?
既然是一个类型的题目,我们首先来了解下滑动窗口的2个概念:
滑动:指一个区间往一个方向进行移动,本题中使用从左到右的方式进行滑动。
窗口:也就是一个区间,这个区间可能会增大,也可能会缩小,也可能是固定的。在本题中,我们可以使用队列来表示窗口,这个队列可大可小,要求其最大值。
但是光有这两个概念根本解决不了本题,我们还缺什么呢?
是的,是窗口要如何变化,如何变大或者缩小。这是问题的核心。
对于字符串abcabcbb,一开始肯定是将a放到队列中,接着放入b,每次放入字符的时候,我们都要检查队列里面有没有相同的字符。显然,光有滑动窗口是不够的,我们还需要一个数据结构来记录队列里面是否存在某个字符,于是我们加入辅助的结构set。
如果每次放入一个字母,我们就看set中有没有,如果没有,那么我们可以直接放;如果存在,我们需要先找到之前的字母位置,并且把这个字母连带它前面的字符都出队列,这样我们才能放入新的字母。
1 采用set记录是否重复。
2 重复了要删除前字母,删除前字母会将窗口左边界右移。
3 新字母会让窗口右边界右移一位。
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
if (s.size() == 0)
return 0;
unordered_set<char> hash;
int m = 0;
int left = 0;
for (int i = 0; i < s.size(); i++) {
// 存在就删除到存在的元素处
while (hash.find(s[i]) != hash.end()) {
hash.erase(s[left]);
left++;
}
// 更新最长区间
m = max(m, i - left + 1);
// 插入新元素
hash.insert(s[i]);
}
return m;
}
};