题目描述
- 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度
- 假设字符串中只包含
'a' ~ 'z' 的字符
- 例如，在字符串
"arabcacfr" 中，最长的不含重复字符的子字符串是 "acfr"，长度为 4
题目解读
代码
leetcode 原题
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char, int> mp;
int res = 0;
int start = -1;
for (int i=0; i<s.size(); ++i) {
if (mp.find(s[i]) != mp.end()) {
start = max(start, mp[s[i]]);
}
mp[s[i]] = i;
res = max(res, i-start);
}
return res;
}
};
#include <iostream>
#include <map>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s){
if (s.empty()){
return 0;
}
map<char, int> mp;
int maxLength = 0; // 最长不含重复字符的字符串长度
int curLength = 0; // 当前不含重复字符的字符串长度
for(int i=0; i < s.size(); i++){
// 第 i 个字符之前没有出现过
if(mp.find(s[i]) == mp.end()){
curLength++;
}
// 第 i 个字符之前出现过
else if(i-mp[s[i]] <= curLength){ // d <= f(i-1)
maxLength = maxLength > curLength ? maxLength:curLength;
curLength = i - mp[s[i]];
}
else{ // d > f(i-1)
curLength++;
}
mp[s[i]] = i;
maxLength = maxLength > curLength ? maxLength:curLength;
}
return maxLength;
}
};
int main(){
Solution ss;
string str = "arabcacfr"; // 4 acfr
// string str = "bbbbbb"; // 1
cout<<ss.lengthOfLongestSubstring(str);
}
总结展望
- 不错
- 字节跳动一面挂在了这道题目上，真是欲哭无泪，今天痛定思痛，把这个问题解决了，再次看书，书上的思路确实优秀，
- 由于篇幅限制，我就不多说了，好好看书啊
