Leecode3——无重复字符的最长子串
程序员文章站
2022-07-12 12:10:15
...
题目说明:
如,在”abcabcbb”中,其无重复字符的最长子字符串是”abc”,其长度为 3;
对于,”bbbbb”,其无重复字符的最长子字符串为”b”,长度为1。
基本思路:
遍历该字符串,往集合里面插入元素;
(1)插入成功,说明无重复,继续插入;
(2)插入不成功时,元素有重复,记录当前最大长度,查找与当前元素重复的前面重复元素的下标,并清空集合,并从该下标的下一个位置继续插入元素,继续(1)(2)过程,直到遍历到字符串的尾部,返回最大的长度。
leetcode提交超时
#include<iostream>
#include<string>
#include<set>
using namespace std;
int main(){
string str;
cin>>str;
if(str.length() == 0)
return 0;
set<char> S;
int max_len = INT_MIN;
for(int i=0;i<str.length();){
if(!S.count(str[i])){
S.insert(str[i]);
}else{//插入失败,说明有重复元素,记录当前元素在str中的位置
int cur_len = S.size();
max_len = (cur_len > max_len) ? cur_len : max_len;
for(int j=i-cur_len;j<i;j++){
if(str[j]==str[i])
i=j;//记录下出现重复元素时前面的重复元素对应的下标
}
S.clear();//清空set,重新插入元素
i++;//从当前重复元素的下一个位置开始重新插入set
}
}
cout<<max_len<<endl;
return 0;
}
第二种方法通过
分别用left和right记录当前遍历过但未出现重复元素的左右下标,如果存在出现重复元素,直接删除重复元素,删除到与当前遍历的元素不重复为止。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.length() == 0)
return 0;
set<char> S;
int left = 0, right = 0, res = 0;
while(right < s.length()){
if(!S.count(s[right])){//判断插入是否重复
S.insert(s[right ++]);
res = max(res, (int)S.size());
}else{
S.erase(s[left++]);//删除重复元素(通过值删除),并记录左下标
}
}
return res;
}
};
下一篇: leetcode14双周赛