DuangDuangDuang，每日一道LeetCode，今天是第三天，可惜部落格沒時間寫了。明天再補上。
今日份題目
給定一個字串，請你找出其中不含有重複字元的 最長子串 的長度。
示例 1:
輸入： “abcabcbb”
輸出： 3
解釋： 因為無重複字元的最長子串是 “abc”，所以其長度為 3。
示例 2:
輸入： “bbbbb”
輸出： 1
解釋： 因為無重複字元的最長子串是 “b”，所以其長度為 1。
示例 3:
輸入： “pwwkew”
輸出： 3
解釋： 因為無重複字元的最長子串是 “wke”，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，”pwke” 是一個子序列，不是子串。
思考
先設第一個字元為子串，第一個字元（或子串）是否包含第二個字元，如果不包含，子串設定為arr［0］+arr［0］，繼續類比子串和字串的第三個字元，累加上去，一直到子串包含字串陣列中後一個字元為止。在設定長度為子串。length。然後第二個字元開始…第三個字元開始…
實現
根據自己的想法coding起來，程式碼還是用的JavaScript~。
程式碼如下：
經驗告訴我們第一次提交大機率是通不過的：
提交一陣亡
好吧，要判斷下輸入引數的長度，在第三行加了句程式碼如下：
等於0或1都直接返回長度就行。
提交二陣亡，很奇怪，為啥au會返回0？因為maxChildStr［i］。indexOf（s。charAt（j）） == -1這個判斷一直成立，所以max沒有賦值到。於是debug程式碼如下
把三元運算子改if了，因為執行效率還是if快。這樣子保證每一次判斷都會給max賦值。
提交三透過，執行用時：644 ms ，記憶體消耗：54 MB。
學習題解
官方給出了三種解題方案，
暴力法
滑動視窗
最佳化的滑動視窗
滑動視窗
暴力法就是我們上述的那種方法，滑動視窗是啥？看了下官方的介紹不是很懂（似懂非懂，因為他沒有給你實踐）：
透過使用 HashSet 作為滑動視窗，我們可以用 O（1）O（1） 的時間來完成對字元是否在當前的子字串中的檢查。
滑動視窗是陣列/字串問題中常用的抽象概念。 視窗通常是在陣列/字串中由開始和結束索引定義的一系列元素的集合，即 ［i， j）［i，j）（左閉，右開）。而滑動視窗是可以將兩個邊界向某一方向“滑動”的視窗。例如，我們將 ［i， j）［i，j） 向右滑動 11 個元素，則它將變為 ［i+1， j+1）［i+1，j+1）（左閉，右開）。
回到我們的問題，我們使用 HashSet 將字元儲存在當前視窗 ［i， j）［i，j）（最初 j = ij=i）中。 然後我們向右側滑動索引 jj，如果它不在 HashSet 中，我們會繼續滑動 jj。直到 s［j］ 已經存在於 HashSet 中。此時，我們找到的沒有重複字元的最長子字串將會以索引 ii 開頭。如果我們對所有的 ii 這樣做，就可以得到答案。
直接看程式碼反而能夠理解了：
我們知道滑動視窗？管他是啥，就當他是是［i，j］的一個區間，從i到j之間的數，所以這裡i比較小，在字串陣列左邊，j比較大，在陣列右邊。然後去理解下核心程式碼：
如果子串set不存在s［j］（我們這裡就直接把字串類比做陣列），我們就把s［j++］也加入到子串中，這樣那個滑動串列埠的長度就會邊長，比如說一開始是［］變成s［0］，然後第二輪，注意上輪有個j++，這時j=1了，判斷是否存在s［1］，還不存在，滑動串列埠就從［0，0］變成［0，1］了，j一直增加，如果子串中沒有重複字元，滑動視窗就會越來越大。然後一直到存在重複，就跳到else，set。remove（s。charAt（i++））； 這個時候i還是等於0，相當於刪掉子串第一個字元，一直刪掉重複的那個為止。不重複了，j又開始增長，直到j到達字串長度為止。這中間最大的j-i就是最長的子串長度了。
好了，理解了就寫出js的程式碼：
執行用時：156 ms 記憶體消耗：39。7 MB。快了很多。
最佳化的滑動視窗
上述的方法最多需要執行 2n 個步驟。事實上，它可以被進一步最佳化為僅需要 n 個步驟。我們可以定義字元到索引的對映，而不是使用集合來判斷一個字元是否存在。 當我們找到重複的字元時，我們可以立即跳過該視窗。
也就是說，如果s［j］s［j］在［i，j）［i，j）範圍內有與j’重複的字元，我們不需要逐漸增加i。我們可以直接跳過［i，j’］範圍內的所有元素，並將i變為j’+1。
關鍵在理解這個j’，這個j’是和j重複的那個數，比如qwerfse，這個j’就是qwe的那個e，i就設成qwer的那個r，即j’+1。這麼一說懂了吧23333。
coding如下：
執行用時：140 ms 記憶體消耗：40 MB。 表示每次提交花的時間都不一樣…
好了，今天的演算法學習到這裡了，完。
希望這篇文章能給你帶來知識和樂趣，喜歡博主的文章可以關注博主哦
