最长无重复子串

最长重复子串 不一样的是,此问题要求所有子串中 没有重复字母的 子串中长度最长为多少。

题目来源 为 Leetcode 第三题 Longest Substring Without Repeating Characters

  • 基本思路是用的滑动窗口来遍历每个起始点的 无重复子串的 长度 , 然后取得最大的长度。

首先来个简单易懂的 每次清空hash表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int lengthOfLongestSubstring(string s) {
string str = s;
int max = 0;
for(int i = 0; i < str.length(); ++i)
{
unordered_map<char,int> map;
map[str[i]] = 1;
int j = 0;
for(j = i+1; j < str.length() && map[str[j]] != 1; ++j)
{
map[str[j]] = 1;
}
if(j - i > max)
{
max = j - i;
}
}
return max;
}

同样的思路,来个升级版 时间复杂度 O(2n) abababababab这种为最坏情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int lengthOfLongestSubstring(string s) {
string str = s;
int max = 0;
const int len = str.length();
int i = 0, j = 0;
unordered_map<char,int> map;
while(i < len && j < len)
{
if(map[str[j]] == 1)//左边前移 区间变短
{
map[str[i++]]--;
}
else//右边前移 区间变长 更新 max
{
map[str[j++]]++;
if(j - i > max)
max = j - i;
}

}
return max;
}

T B
站点访问量: / , 本页阅读量:
T B