Given a string, find the length of the longest substring without repeating characters.
Note
that the answer must be a substring,"pwke"
is a subsequence and not a substring.
Example 1:
Example 2:
Example 3:
Related Topics: Hash Table
、String
這題是給定一個字串,從中找出一最長子字串,且子字串中不包含重複字元。
我這題使用 Sliding Window 來解,一開始將 start
與 end
指標指在起始位置( index=0 ),每輪 end
指標移動一格納入一個新的字元,在納入新字元後,檢查新字元是否已經存於 Window 中。
若有,則更改 start
位置,將指標移動到第一個重複字元的下一個位置。若無,則 start
停留在原位,最後記錄總長度並結束此輪。直到字串輪巡結束後回傳最長長度。
理論上是這樣啦,不過實做上為了效能考量這邊使用了 HashMap 來記錄,實做步驟如下:
初始化一個 HashMap indexes ,用以記錄目前出現過的字元,與其對應的下標。
開始輪巡整個字串,每一輪讀入一個新的字元,若該字元存於 indexes,則判斷記錄的下標是大於 start ,若大於 start 則更新 start 所指向的位置。
每一輪結束時,記錄最長的長度並更新新字元於 indexes 所記錄的下標。
本文作者: 辛西亞.Cynthia
本文連結: 辛西亞的技能樹 / hackmd 版本
版權聲明: 部落格中所有文章,均採用 姓名標示-非商業性-相同方式分享 4.0 國際 (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處!