LeetCode --- 无重复字符的最长子串

题目描述

无重复字符的最长子串

找到无重复的最长连续字符串。

示例1中 abc | bca | cab 都符合题意。输出3即可。

代码

可以使用暴力枚举 + 哈希表，哈希表来判断是否重复，枚举来判断每一种情况，需要开两层for循环，时间复杂度n^2。

1. 每次循环，都直接将字符入队，并在hash中存下该字符出现过的个数
2. 如果hash[s[i]]出现的次数超过了1次，就需要出队，将队头删除，直到hash[s[i]] == 1
3. 此时队列中的字符出现的次数一定不会重复，找到一个最大的队列长度

假如现在队列中为abc，下一次入队的是字符b，那么b字符就出现了两次，需要出队，直到字符b出现的次数为1次。删除队头a，此时队列为bcb，继续出队变成cb，b出现的次数就变成1次了。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxq = 0;
        unordered_map<char, int> hash;
        queue<char> 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 = max<int>(maxq, q.size());
        }
        return maxq;
 
    }
};