力扣算法题Day3
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
1
2
3
| 输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
示例 2:
1
2
3
| 输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
示例 3:
1
2
3
4
| 输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
提示：
0 <= s.length <= 5 * 104s 由英文字母、数字、符号和空格组成
解题思路：
首先要用一个max去记录无重复字符的最长子串的长度，初始化为0。
然后定义个map用来装无重复字符的最长子串。
然后开始正式遍历，按照顺序读取字符串s的每个字符，装入map中，如果map中已经有重复字符，则需要先将map中出现重复字符的位置以及这个重复字符位置之前的字符都要删掉（因为要获取无重复字符的最长子串，这里要结合示例1和示例3理解一下），然后再把当前字符装入map中。
每读取一个字符就需要判断当前无重复字符的子串的长度是否大于max，如果大于则更新max为当前无重复字符的子串的长度。
代码：
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
42
43
44
45
46
47
48
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
int max = 0; // 记录最大字串长度
std::map<char, int> myMap;
for (int i = 0; i < s.size(); i++) { // 循环遍历s
// std::cout << "=======================" << std::endl;
// std::cout << "读第" << i << "个字符" << s[i] << std::endl;
// //读取第i个字符
if (myMap.find(s[i]) != myMap.end()) { // 判断是否出现重复字符
// cout << myMap[s[i]] << "的位置重复" << endl;
// 输出当前map方便查看
// cout << "当前map:" << endl;
// for (std::map<char, int>::iterator it = myMap.begin();
// it != myMap.end(); ++it) {
// std::cout << it->first << " is " << it->second <<
// std::endl;
// }
// 如果map中出现重复字符的位置以及之前的字符都要删掉
for (std::map<char, int>::iterator it = myMap.begin();
it != myMap.end();) {
if (it->second < myMap[s[i]])
{
it=myMap.erase(it);
} else
++it;
}
myMap.erase(s[i]);
// 将新的字符插入
// cout << "添加新的" << s[i] << "位置为" << i << endl;
myMap[s[i]] = i;
} else { // 如果没有出现重复字符，则直接插入map
myMap[s[i]] = i;
}
// 展示读取完一次字符后执行完操作的map
// cout << i << "次读取字符后map:" << endl;
// for (std::map<char, int>::iterator it = myMap.begin();
// it != myMap.end(); ++it) {
// std::cout << it->first << " is " << it->second << std::endl;
// }
// 更新max
if (myMap.size() > max) {
max = myMap.size();
}
}
return max;
}
};
|
