題目描述

無重復字符的最長子串

找到無重復的最長連續字符串。

示例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;}
};