作者:whisper
链接:https://www.proprogrammar.com/article/890
声明:请尊重原作者的劳动,如需转载请注明出处
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
s.length <= 40000
难度:中等;标签:哈希表,双指针,滑动窗口;编程语言:C++
class Solution {
public:
// 想法:用辅助数组
int lengthOfLongestSubstring(string s) {
int aid[256], longest = 0, start = 0, len = s.length();
fill(aid, aid+256, -1);
for(int i = 0; i < len; i++){
if(aid[s[i] - ' '] == -1){
aid[s[i] - ' '] = i;
}else{
longest = max(longest, i - start);
for(int j = start; j <= aid[s[i] - ' '] - 1; j++){
aid[s[j] - ' '] = -1;
}
start = max(start, aid[s[i] - ' '] + 1);
aid[s[i] - ' '] = i;
}
}
return max(longest, len - start);
}
};
用一个数组记录字符第一次出现的位置,用start记录当前无重复字符的子串的开始位置,如果字符再次(第二次)出现,更新结果,同时更新start为字符第一次出现位置之后一个位置,这样该字符在当前子串中只出现一次
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int map[128]={0},len=0,start=0;
for(int i=0;i<s.length();i++){
++map[s[i]];
while(map[s[i]]==2){
--map[s[start++]];
}
len = max(len,i-start+1);
}
return len;
}
};
和我的解法方法是一样的,不过这里代码比较简短,同时也不是很好理解了,理解了我的解法再看这里就比较好理解了(方法是差不多一样的)
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论