題目來源于 LeetCode 的第 3 題，難度為：中等。目前的通過率是37.3%。
解題思路的思考：
以abcabcbb為例，找出以每個字元結束，不包含重複字元的最長子串。那麼其中最長的那個字元串即為答案。對于示例一中的字元串，我們列舉出這些結果，其中括号中表示選中的字元以及最長的字元串：
- 以 [a]bcabcbb 結束的最長字元串為[a]bcabcbb,長度為1
- 以 a[b]cabcbb 結束的最長字元串為[ab]cabcbb,長度為2
- 以 ab[c]abcbb 結束的最長字元串為[abc]abcbb,長度為3
- 以 abc[a]bcbb 結束的最長字元串為a[bca]bcbb,長度為3
- 以 abca[b]cbb 結束的最長字元串為ab[cab]cbb,長度為3
- 以 abcab[c]bb 結束的最長字元串為abc[abc]bb,長度為3
- 以 abcabc[b]b 結束的最長字元串為abcab[cb]b,長度為2
- 以 abcabcb[b] 結束的最長字元串為abcabcb[b],長度為1
有點動态規劃的意思了，但是不是動态規劃。
我們每次找以x結尾的最長子串的時候，都是在上次的最長子串的基礎上進行查找。比如在找以abcabcbb中的第4個a結尾的最長子串的時候，我們從上次的最長子串abc的基礎上找。
以此類推，每次找以x結尾的最長子串的時候，都是以x前面的那位最長子串的基礎上找。比如，本例中的a前的那位是c，c的最長子串是abc。再次基礎上開始我們确定以a結尾的最長子串：
我們假定求以x結尾的最長子串，然後x前的那位結尾的最長子串是 #$%^
找x上次出現的位置
分2種情況：
1、x不在上次的最長子串中，則以x結尾的最長子串就是#$%^x
2、x在上次的最長子串中，則以x結尾的最長子串就是 %^x
一直周遊到結束，傳回最長的那個即可。
代碼
class Solution {
func lengthOfLongestSubstring(_ s: String) -> Int {
if s.count == 0 { return 0 }
var li = 0
var si = 0
var map = [Character:Int]()
map[s.first!] = 0
var maxLength = 1
for (index,char) in s.enumerated() {
if index == 0 { continue }
li = map[char] ?? -1
if li >= si {
si = li + 1
}
maxLength = max(maxLength, index - si + 1)
map[char] = index
}
return maxLength
}
} 代碼解讀
li： lastIndex的縮寫 ,表示：比如abcabcaa 現在到第4個位置也就是a ，li表示上次a出現的位置 li = 1
si: startindex的縮寫，表示以i-1位置字元結尾的最長不重複字元串的開始索引(最左索引) 比如abcabcaa 第三個位置的c，si =0
map 存的就li的value，key 就是character
結尾
這個題其實有點動态規劃的意思，要是有動态規劃的基礎，就可以很好的去解這道題。希望能幫助到大家。
歡迎關注【無量測試之道】公衆号，
Python程式設計學習資源幹貨、
Python+Appium架構APP的UI自動化、
Python+Selenium架構Web的UI自動化、
Python+Unittest架構API自動化、
文章下方有公衆号二維碼，可直接微信掃一掃關注即可。
備注：我的個人公衆号已正式開通，緻力于測試技術的分享，包含：大資料測試、功能測試，測試開發，API接口自動化、測試運維、UI自動化測試等，微信搜尋公衆号：“無量測試之道”，或掃描下方二維碼：