力扣題目鏈接：無重復字符的最長子串

一、題目解析

二、算法原理

解法一：暴力解法（時間復雜度最壞：O(N)）

從每一個位置開始往后枚舉，在往后尋找無重復最長子串時，可以利用哈希表來統計字符出現的頻率，如果出現了重復字符就跳出循環，如果沒有重復則更新結果，這樣枚舉下去找到長度最長的返回即可。

解法二：滑動窗口

?滑動窗口也是定義了兩個指針在移動，但是這兩個指針所指向的區間就像一個滑動的窗口一樣。

滑動窗口的基本步驟

• 定義兩個指針int left=0，right=0;
• 進入滑動窗口——>讓字符進入哈希表
• 判斷條件——>窗口內出現重復字符
• 出滑動窗口——>從哈希表中將字符刪除
• 更新結果

注：結果的更新不一定是放在最后，這個要根據題目的要求進行相應的改變，而且判斷條件是要循環一直判斷，如果滿足就出窗口，不滿足條件循環才停止。

?

?每次移動指針的時候結果都在更新，所以結果不會出錯。

時間復雜度：雖然代碼是兩層循環，但是left指針和right指針都是不回退的，兩者最多都往后移動n次。因此時間復雜度是O(N)。

這個題最大的難度是怎么分析這個問題從而想到要用滑動窗口來解決。?

三、代碼編寫

暴力枚舉

class Solution {
public:int lengthOfLongestSubstring(string s) {int ret = 0;int n = s.size();for(int i = 0; i < n; i++){int hash[128] = {0};//用數組模擬哈希表，統計次數for(int j = i; j < n; j++){hash[s[j]]++;if(hash[s[j]] > 1)//判斷是否重復break;ret = max(ret, j - i + 1);//更新結果}}return ret;}
};

滑動窗口?

class Solution {
public:int lengthOfLongestSubstring(string s) {int ret = 0;int left = 0, right = 0, n = s.size();int hash[128] = {0};//用數組來模擬哈希表while(right < n){hash[s[right]]++;//進窗口while(hash[s[right]] > 1)//判斷{hash[s[left++]]--;//出窗口}ret = max(ret, right - left + 1);//更新結果right++;}return ret;}
};

如有錯誤或不足歡迎大家批評指正。