3. 无重复字符的最长子串（中等）
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例1：
1
2
3
| 输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
示例2：
1
2
3
| 输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
示例3：
1
2
3
4
| 输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
解法一：滑动窗口
通过
1
2
| 执行用时：20 ms, 在所有 C++ 提交中击败了71.14%的用户
内存消耗：7 MB, 在所有 C++ 提交中击败了100.00%的用户
|
思路解析
1
2
3
4
5
6
| 设立左指针a和右指针b
b指针向右侧伸缩｛
对每个A[b]判断是否在之前的数组出现过；
如果出现，指针a指向出现过的位置的下一个位置；
更新右指针和最大长度；
｝
|
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <iostream>
#include <math.h>
#include <iomanip>
#include <unordered_map>
#include <string>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
int lengthOfLongestSubstring(string s)
{
int start(0), end(0), length(0), result(0);
int size = s.size();
while (end < size)
{
char end_word = s[end];
for (int i = start; i < end; i++)
{
if (s[i] == end_word) {
start = i + 1;
length = end - start;
break;
}
}
end++;
length++;
result = length > result ? length : result;
}
return result;
}
int main()
{
string input = "abcabcbb";
int Maxlength = lengthOfLongestSubstring(input);
cout << Maxlength << endl;
return 0;
}
|
复杂度分析：
时间复杂度O(n^2)，空间复杂度O(1)。
解法二：hashmap优化时间
注：map的key存字符，但是value不存什么0或1了。直接存当前的有序下标，解决了多个字母出现的问题。
通过
1
2
| 执行用时：36 ms, 在所有 C++ 提交中击败了60.40%的用户
内存消耗：8.7 MB, 在所有 C++ 提交中击败了100.00%的用户
|
思路解析
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <math.h>
#include <iomanip>
#include <unordered_map>
#include <string>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
int lengthOfLongestSubstring(string s)
{
int start(0), end(0), length(0), result(0);
int sSize = int(s.size());
unordered_map<char, int> hash;
while (end < sSize)
{
char tmpChar = s[end];
if (hash.find(tmpChar) != hash.end() && hash[tmpChar] >= start)
{
start = hash[tmpChar] + 1;
length = end - start;
}
hash[tmpChar] = end;
end++;
length++;
result = length > result ? length : result;
}
return result;
}
int main()
{
string input = "abcabcbb";
int Maxlength = lengthOfLongestSubstring(input);
cout << Maxlength << endl;
return 0;
}
|
复杂度分析：
时间复杂度O(n)，空间复杂度O(n)。
解法三：利用数组（桶）代替hashmap
通过
1
2
| 执行用时：4 ms, 在所有 C++ 提交中击败了99.09%的用户
内存消耗：7.9 MB, 在所有 C++ 提交中击败了100.00%的用户
|
思路解析
1
| 判断是否出现过时，利用桶来代替hashmap优化时间。
|
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <math.h>
#include <iomanip>
#include <unordered_map>
#include <string>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
int lengthOfLongestSubstring(string s)
{
int start(0), end(0), length(0), result(0);
int sSize = int(s.size());
vector<int> vec(128, -1);
while (end < sSize)
{
char tmpChar = s[end];
if (vec[int(tmpChar)] >= start)
{
start = vec[int(tmpChar)] + 1;
length = end - start;
}
vec[int(tmpChar)] = end;
end++;
length++;
result = length > result ? length : result;
}
return result;
}
int main()
{
string input = "abcabcbb";
int Maxlength = lengthOfLongestSubstring(input);
cout << Maxlength << endl;
return 0;
}
|
复杂度分析：
时间复杂度O(n)，空间复杂度O(n)。