最长不含重复字符的字符串(备忘)
双指针
C++ 代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(!s.size())return 0;
if(s.size() == 1)return 1;
unordered_map<char, int> dict;
int maxl = 0;
for(int i = 0, j = 0; j < s.size(); j ++ ){
dict[s[j]] ++ ;
if(dict[s[j]] > 1){
while(dict[s[i]] == 1)dict[s[i ++ ]] -- ;
dict[s[i ++ ]] -- ;
}
maxl = max(maxl, j - i + 1);
}
return maxl;
}
};
动态规划
C++ 代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0)return 0;
int curLength = 0;
int maxLength = 0;
unordered_map<char, int> position;
for(auto x : s)position[x] = -1;
for(int i = 0; i < s.size(); i ++ ){
int pre = position[s[i]];
if(pre < 0 || i - pre > curLength)
++ curLength;
else{
if(curLength > maxLength)
maxLength = curLength;
curLength = i - pre;
}
position[s[i]] = i;
}
if(curLength > maxLength)
maxLength = curLength;
return maxLength;
}
};