网站后台管理系统页面,php网站开发需求文档,免费企业网站源码,wordpress CPT UI题目描述
无重复字符的最长子串 找到无重复的最长连续字符串。
示例1中 abc | bca | cab 都符合题意。输出3即可。
代码
可以使用暴力枚举 哈希表#xff0c;哈希表来判断是否重复#xff0c;枚举来判断每一种情况#xff0c;需要开两层for循环#xff0c;时间复杂度n…题目描述
无重复字符的最长子串 找到无重复的最长连续字符串。
示例1中 abc | bca | cab 都符合题意。输出3即可。
代码
可以使用暴力枚举 哈希表哈希表来判断是否重复枚举来判断每一种情况需要开两层for循环时间复杂度n^2。
每次循环都直接将字符入队并在hash中存下该字符出现过的个数如果hash[s[i]]出现的次数超过了1次就需要出队将队头删除直到hash[s[i]] 1此时队列中的字符出现的次数一定不会重复找到一个最大的队列长度
假如现在队列中为abc下一次入队的是字符b那么b字符就出现了两次需要出队直到字符b出现的次数为1次。删除队头a此时队列为bcb继续出队变成cbb出现的次数就变成1次了。
class Solution {
public:int lengthOfLongestSubstring(string s) {int maxq 0;unordered_mapchar, int hash;queuechar q;int n s.size();for (int i 0; i n; i){q.push(s[i]);hash[s[i]];while (hash[s[i]] 2){char c q.front();q.pop();if (hash[c] ! 0)hash[c]--;}maxq maxint(maxq, q.size());}return maxq;}
};
