3 無重復(fù)字符的最長子串
方法一：哈希表
使用哈希表，以鍵值對的方式存儲 （單字符，該字符位序）。一次遍歷，不重復(fù)則存入哈希表并且使用滑動(dòng)數(shù)組更新最大長度，否則讀取第一次出現(xiàn)的下標(biāo),從該位置的下一個(gè)位序繼續(xù)遍歷，并且清空整個(gè)哈希表；
Python版本
C++版本
復(fù)雜度分析
時(shí)間復(fù)雜度：
O(N)。此處的n指的是字符數(shù)組s的長度。空間復(fù)雜度：
O(C)。字母最多有26種，因此最大非重復(fù)子串的長度為26。
方法一：滑動(dòng)窗口
分別初始化左右指針，右指針初始化為-1，左指針為0；內(nèi)部while循環(huán)枚舉不重復(fù)字符串，for循環(huán)枚舉重復(fù)時(shí)，應(yīng)當(dāng)去除的左邊界字符，每當(dāng)遇到重復(fù)字母時(shí)，更新最大長度。
Python版本
C++版本
復(fù)雜度分析
時(shí)間復(fù)雜度：O(N)。此處的n指的是 s 字符串長度。
空間復(fù)雜度：O(C)。非重復(fù)字符，包含四大類別，以ASCⅡ碼值作標(biāo)的，不超過128；
備注
集合替換哈希表，數(shù)據(jù)量縮小一半；
雙指針遍歷，且使用指針計(jì)算最大長度，去除長度計(jì)算與容器的關(guān)聯(lián)，無需清空容器；
一次遍歷無須回退。
關(guān)于滑動(dòng)窗口的補(bǔ)充
已知滑窗大小k的情況下，枚舉滑窗右端點(diǎn)，根據(jù)滑窗大小可以推理，得到左端點(diǎn)的值
滑窗大小為求解對象時(shí)，左右指針如何初始化便于遍歷？
左右指針均初始化為0
左指針初始為0,刪除操作從
index = 1開始，右指針初始化為-1兩種初始化的比較：
后者的優(yōu)越性體現(xiàn)在哪里？
遍歷時(shí)無需考慮對兩種情況的特判：1. 左指針不動(dòng)，右指針向右移動(dòng)（遇到字符連續(xù)且非重復(fù)）2. 左指針向右移動(dòng)一位，右指針移動(dòng)兩位（遇到：當(dāng)前字符與容器中左端點(diǎn)字符重復(fù)）；其次盡可能做到不重不漏。
哪一種方式更加符合數(shù)學(xué)常理呢？
使用滑動(dòng)窗口元素個(gè)數(shù)的計(jì)算公式
sclae = right - left + 1，對于前者，當(dāng)指向同一個(gè)位序時(shí)，元素個(gè)數(shù)為1，對于后者，當(dāng)左右指針分別指向0，-1時(shí)，元素個(gè)數(shù)scale = (-1) - 0 + 1 = 0，數(shù)學(xué)意義上更加嚴(yán)謹(jǐn)思考滑動(dòng)窗口的本質(zhì)是什么？
本質(zhì)是一個(gè)區(qū)間，如果兩個(gè)指針指向同一個(gè)位序，視覺上等價(jià)于區(qū)間為空；
刷題過程
V1
rate: 282/987
wrong case: "pwwkew" ?expected result: 3 specifical result: 4
重定向的時(shí)候，應(yīng)該清空整個(gè)容器，否則對于樣例ACCDEF來說，本來應(yīng)該取CDEF，由于之前僅刪除了ACC中的第二個(gè)，字典中還存留一個(gè)A，導(dǎo)致實(shí)際輸出結(jié)果比預(yù)期結(jié)果大1
?
V2
AC版本
V3
rate: 945/987
wrong case aab， expected result: 2, factual result: 1
V4
27 / 987
繼續(xù)修改：用雙指針計(jì)算距離，進(jìn)一步削弱容器的作用
反思：還是按照回退的思路移動(dòng)指針，卻沒有修改容器中的元素，二者強(qiáng)關(guān)聯(lián)；
chatGPT優(yōu)化版本
考慮優(yōu)化字典的使用。
在這段代碼中，每當(dāng)出現(xiàn)重復(fù)元素時(shí)，都需要將整個(gè)字典清空，相當(dāng)于把已經(jīng)掃描過的字符的位置信息全部丟棄。
為了避免這種浪費(fèi)，我們可以將字典改為記錄每個(gè)字符上一次出現(xiàn)的位置，而不是第一次出現(xiàn)的位置。這樣，當(dāng)我們找到重復(fù)元素時(shí)，可以直接將left指針跳到該元素上一次出現(xiàn)的位置的下一個(gè)位置，從而避免了清空字典的操作。
在具體實(shí)現(xiàn)時(shí)，不管字符是否在字段中出現(xiàn)，均將其添加到字典中；
對于已經(jīng)在字典中出現(xiàn)的字符，將left指針跳到該字符上一次出現(xiàn)的位置的下一個(gè)位置，更新該字符在字典中的索引，并且求出當(dāng)前子串長度并更新maxLen。
這樣的優(yōu)化可以進(jìn)一步提高代碼的效率，時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(min(n,m))，其中m為字符集大小。
修改后的代碼如下：
思考中文字整理
不定長字符串，字符串長度即 K 就是我們要求的值
字符串的特征：四種類型，字母，數(shù)字，符號和空格
數(shù)據(jù)結(jié)構(gòu)：set()自帶去重
len(set(nums)) = 1, result = 1
目標(biāo)數(shù)據(jù)特征：
連續(xù)，且元素不重復(fù) 如何確保連續(xù)？順序遍歷 不重復(fù)？集合
如何計(jì)算？如果出現(xiàn)連續(xù)字符，則清空集合；非重，則繼續(xù)遍歷，更新最大長度為集合長度，
如果在當(dāng)前元素重復(fù)，準(zhǔn)備回退時(shí)不清空哈希表，那么已經(jīng)在哈希表的元素會直接影響，顯然，回退時(shí)，可以不刪除重復(fù)元素-位序這組鍵值對嗎？不能，如果未刪除，將陷入死循環(huán)，在一個(gè)字符兩次出現(xiàn)的位置反復(fù)遍歷；
當(dāng)出現(xiàn)第一個(gè)同種字符時(shí)，清空集合后應(yīng)該再插入該字符，這個(gè)字符可能作為下一個(gè)連續(xù)不重復(fù)字符串的頭部，后來將這個(gè)思路轉(zhuǎn)化為后退到某個(gè)字符第一次出現(xiàn)位置的下一個(gè)，那么無需再插入一個(gè)元素維持平衡
407/987 由于一次遍歷，不能重定向起始位置，而是順著重復(fù)字符繼續(xù)向下尋找，而可能出現(xiàn)重復(fù)字母不連續(xù)，兩個(gè)字母之間存在間隔的情況
此時(shí)應(yīng)該重定位，從重復(fù)字母首次出現(xiàn)的位置的下一個(gè)位置繼續(xù)遍歷，而不是順著當(dāng)前位置【某個(gè)字符第二次出現(xiàn)】繼續(xù)遍歷
計(jì)算：即使重定位，那么之前按照字典長度來計(jì)算最長子字符串，不會影響結(jié)果，只有本次遍歷到的子字符串更長，才能添加進(jìn)去，從而改變長度
marked: 以后能否自己構(gòu)造測試樣例，自我折磨呢？
有沒有一種結(jié)構(gòu)，既可以判斷重復(fù)，又可以滿足回退，此時(shí)回退的是當(dāng)前字符第一次出現(xiàn)的位置，可是我們?nèi)绾谓o它定界呢？
所以用兩個(gè)指針來處理字符以及字符回退的問題，但是容器能夠和雙指針搭配嗎?回退的時(shí)候，如何保證位序和元素的一致性呢？進(jìn)一步思考：一致性表達(dá)的是，當(dāng)回退的時(shí)候，退到那個(gè)位置，并且集合中已有的元素如何處理？
能不能直接用指針計(jì)算目標(biāo)字符串的長度，從而擺脫對集合的操作？
現(xiàn)在的循環(huán)是一次 while 加判斷，可以寫成 for 內(nèi)嵌 while,那么可以保存非重復(fù)字串的左右字符，這不就可以驗(yàn)證重復(fù)【此舉仍然會將復(fù)雜度推到 O(N^2)
先定義 left 和 right ？此題與滑動(dòng)窗口之間的關(guān)聯(lián)？可將最長非重復(fù)子串看做是 k，非重復(fù)的最后一個(gè)子母看做是滑窗的右端點(diǎn)，最長非重復(fù)子串的開始位置看做是左端點(diǎn) 如何滑動(dòng)？仍然通過指針滑動(dòng)，判斷的條件是字符是否重復(fù)，即是否已經(jīng)被包含在哈希表中
