無重復字符的最長子串

題目鏈接：3. 無重復字符的最長子串 - 力扣（LeetCode）

給定一個字符串 s ，請你找出其中不含有重復字符的最長子串的長度。

輸入: s = "abcabcbb"

輸出: 3

解釋: 因為無重復字符的最長子串是"abc"，所以其長度為 3。

思路解析：

本題的暴力解法為兩層for循環遍歷+hash判斷是否重復，時間復雜度為O(N^2)，根據暴力解法可以進一步優化將時間復雜度降低到O(N)

以示例數組為例

正向性：定義一個left和一個right指針，二者指向第一個字符。在遍歷的過程中，right指針向右移動，直到遇到一個已經出現的字符停止，此時right指針是否需要回退呢？答案是不需要，因為當right指針遇到已經出現過的字符后，left指針就會開始移動，如果left++，則下一個字符為b，此時在區間(left=1)[left, right]中不存在已經重復的字符，因為已經跳過了重復的字符a。所以，left指針和right指針在移動的過程中均滿足從左向右移動不回退

在上面的示例中，重復字符為第一個字符，考慮示例：s="deabcabcbb"。在該示例中，right向右移動一直到第二個字符a，此時[left, right]中存在重復字符a，停止移動right，接下來移動left，那么left是否需要一次只移動1個長度呢？不需要，原因很簡單，left++后下一個區間(left=1)[left, right]起始字符為e，而對應區間中的子串為eabca，仍然存在重復字符a，所以left在移動時并不是每一次都只移動1個長度（即只循環一次），只需要讓left移動到當前區間第一個重復字符的下一個字符b的位置即可，所以需要使用循環來讓left一直移動直到跳過重復字符

對于哈希表的處理，不需要使用庫中的結構，因為題目中給出了結果s的取值只會出現英文字母、數字、符號和空格，所以只需要定義一個長度為128的數組即可，對應的下標即為對應字符的ASCII碼值

根據上面的分析，因為left和right在遍歷的過程中不需要回退，所以可以考慮使用滑動窗口算法解決，步驟如下：

1. 進窗口：本題進窗口意味著只要元素沒有在哈希表數組中就進入哈希表數組

2. 判斷：因為遇到重復的字符right就停止移動，所以當哈希表數組字符ASCII值下標對應的元素不為0即代表重復，作為判斷條件

3. 出窗口：出窗口則意味著已經在哈希表中的元素需要離開哈希表，并讓left向后移動，需要注意的是，因為需要進入一個新的窗口，所以出窗口時需要使left位置的字符對應哈希數組下標值的元素出現的次數改變

4. 更新結果：本題更新結果只需要在[left, right]區間沒有重復字符后即可，用變量len存儲子串長度，再移動right

具體步驟如下：

參考代碼：

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0}; // 創建hash表int len = 0;for(int left = 0, right = 0; right < s.size(); right++){hash[s[right]]++; // 標記已經出現// 判斷while(hash[s[right]] > 1){hash[s[left++]]--;// 出窗口}len = max(len, right - left + 1);// 更新結果}return len;}
};