题目描述
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
样例
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
算法1
(记录重复字符下标的哈希) $O(n)$
这种方法缺点就是不太直观,因为要用0来表示没有出现过该字符,因此哈希里的下标都要加1
C++ 代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size()==1)
return 1;
int j=0,l=0;
unordered_map<char,int> win;//键:字符 值:上次出现的位置(下标+1,因为0要表示没有出现的状态,不能用来表示位置)
for(int i=0;i<s.size();i++)
{
if(win[s[i]])//已经出现过一次,即重复字符
for(;j<win[s[i]];j++)
win[s[j]]=0;//把出窗的字符记录消去
win[s[i]]=i+1;//添加入窗字符的记录
// cout<<j<<" "<<i<<endl;
l=max(l,i-j+1);
}
return l;
}
};
算法2
(记录不同种字符出现次数的哈希) $O(n)$
与方法1不同的地方在于建立的哈希映射不一样。写法较直观。
C++ 代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> hash;
int res = 0;
for (int i = 0, j = 0; j < s.size(); j ++ )
{
hash[s[j]] ++ ;
while (hash[s[j]] > 1) hash[s[i ++ ]] -- ;
res = max(res, j - i + 1);
}
return res;
}
};