从头到尾遍历所有字符,用一个队列存当前字符为结尾的最长字符串。
class Solution { public: int lengthOfLongestSubstring(string s) { if(s.empty()){//若s是空字符串 return 0; }else{ int maxSize = 0; int temp; vector<char> queue; for(int i=0;i<s.size();i++){ temp = pushChar(queue,s[i]); if(maxSize<temp){ maxSize = temp; } } return maxSize; } } int pushChar(vector<char>& q,char c){//这里函数中对q的处理的影响范围? for(vector<char>::iterator i=q.begin();i!=q.end();i++){ if(*i==c){ q.erase(q.begin(),i+1);//注意要迭代器指向被最后删除的元素的下一个元素 break; } } q.push_back(c); //cout<<c<<endl; //cout<<q.size()<<endl; return q.size(); } };
时间复杂度:n为原字符串长度,时间复杂度为n2。外层循环遍历原字符串所有字符,内层循环遍历队列长度。队列长度最差情况是0,1,到n-1。整个最差情况是0+1+2+...+n-1,也就是n2/2。
空间复杂度:n为原字符串长度,空间复杂度为n。需要一个队列来存储以当前遍历到的字符为结尾的最长不重复字符串。
官方题解中的思路和我有些差别:找出从每一个字符开始的,不包含重复字符的最长子串。
其中的要点在于上一个字符开始的最长子串中从当前字符开始到末尾的字串是一定不重复的。
官方题解中还用到了哈希集合这个数据结构,便于判断重复。
官方的方法比我的方法在时间复杂度的分析,原因在于:
常用操作(count,insert,erase)
原文:https://www.cnblogs.com/BoysCryToo/p/13266331.html