Given a string, find the length of the longest substring without repeating characters.
给定一个字符串,找到最长无相同字符连续子串的长度
举例:
对于字符串"abcabcbb",答案为"abc",长度为3.
对于字符串"bbbbb",答案为"b",长度为1.
对于字符串"pwwkew",答案为"wke",长度为3.
注意答案必须为连续子串,pwke为子串,但不是连续子串
拟采用方法:
创建一个数组,记录每个字符对应最后出现的位置
维护以第i位为字符串末尾的最长满足条件子字符串
如果第i位为字符x,x未出现过,则cur++,否则cur=min(cur+1,两个x间距离)
代码如下:
class Solution {
public:
int min_comp(int a, int b){
return a > b ? b : a;
}
int max_comp(int a, int b){
return a > b ? a : b;
}
int lengthOfLongestSubstring(string s) {
int len = s.length();
int cur = 0;
int max = 0;
int chara[300] = {0};
char word;
for(int i = 0; i < len; i++){
word = s[i];
cur = min_comp(cur + 1, i + 1 - chara[word]);
chara[word] = i + 1;
max = max_comp(cur, max);
}
return max;
}
};
此题中不止有小写字母,一开始只考虑了小写字母,开了30位,然后数组溢出了
网友评论