暴力解法，枚举所有子字符串组合
输入：长度[0,n]的字符串
耗时过长---
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
int ans = ;
if(s.empty()){
return ;
}
for(int i = ; i < len-; i++){
for(int j = i+; j < len; j++){
if(allUnique(s, i, j)){
ans = max(ans, j-i+);
}
}
}
return ans;
}
bool allUnique(string ss, int start, int end){
std::set<char> ss_set;
for(int i = start; i <= end; i++){
char ch = ss[i];
if(ss_set.count(ch)){
return false;
}
ss_set.insert(ss[i]);
}
return true;
}
};
第二种方法：改进暴力解法
子字符串为[i,j)，左闭右开。一旦检测到新加入字符已存在于已有子字符串中，则返回当前子字符串长度，清空子字符串，左边界右移（i+1），重新生成新的子字符串。
依然耗时过长
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
std::cout << "len is : " << len << std::endl;
int ans = ;
std::set<char> ss_set;
int begin = ;
if(s.empty()){
return ;
}
else{
while(begin < len-) {
//std::cout << "begin is : " << begin << std::endl;
int tmp = ;
ss_set.clear();
for(int j = begin; j < len; j++){
if(ss_set.count(s[j])){
break;
}
ss_set.insert(s[j]);
tmp++;
}
begin = begin + ;
ans = max(ans, tmp);
}
}
return ans;
}
};
第三种：滑窗法
改进第二种方法。子字符串为[i,j)，左闭右开。一旦检测到新加入字符已存在于已有子字符串中，则返回当前子字符串长度，删除begin位置的字符，窗口右移（i+1，count-1），新加入字符与窗口中的元素进行对比。
耗时94ms，消耗内存21.3MB
TIP：
1. 通过使用 HashSet 作为滑动窗口，我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查;
2. 滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j) 向右滑动 11 个元素，则它将变为 [i+1,j+1)（左闭，右开）。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
std::set<char> ss_set;
int ans = , begin = , count = , index = ;
set<char>::const_iterator iter;
if(s.empty()){
return ;
}
else{
while(begin < len-) {
for(int j = index; j < len; j++){
if(ss_set.count(s[j])){
index = begin + count;
break;
}
ss_set.insert(s[j]);
count++;
}
// for(iter = ss_set.begin(); iter != ss_set.end(); iter++){
// std::cout << *iter << " " ;
// }
// std::cout << std::endl;
ss_set.erase(s[begin]);
begin = begin + ;
ans = max(ans, count);
count = count - ;
}
}
return ans;
}
};
滑窗法比较清晰的表达，引入变量i，j表示窗口的范围。
注意 i++ 和 ++i 的区别
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
std::set<char> ss_set;
int ans = , i = , j = ;if(s.empty()){
return ;
}
else{
while(i < len && j < len){
if(!ss_set.count(s[j])){
ss_set.insert(s[j++]);
ans = max(ans, j-i);
}
else{
ss_set.erase(s[i++]);
}
}
}
return ans;
}
};
优化滑窗法
我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。
也就是说，如果 s[j] 在 [i,j) 范围内有与 j′ 重复的字符，我们不需要逐渐增加 i 。 我们可以直接跳过 [i，j′] 范围内的所有元素，并将 ii 变为 j' + 1j′+1。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
int ans = , i = , j = ;
map<char, int> str_map;
for(j; j < len; j++){
if(str_map.count(s[j])){
i = max(i, str_map.find(s[j])->second);
}
ans = max(ans, j - i + );
str_map[s[j]] = j+; //窗口右边界右移
}
return ans;
}
};