前言
我們社區(qū)從本期開始會將顧毅（Netflix 增長黑客，《iOS 面試之道》作者垢袱，ACE 職業(yè)健身教練。微博:@故胤道長)）的 Swift 算法題題解整理為文字版以方便大家學習與閱讀。
不積跬步扫责，無以至千里；不積小流逃呼，無以成江海鳖孤，Swift社區(qū) 伴你前行者娱。
1. 描述
給定一個字符串 s, 找出最長未重復的子字符串的長度.
2. 示例
示例 1
輸入： s = "abcabcbb"
輸出： 3
解釋： 最長為重復的子字符串答案是 "abc", 長度為 3.
示例 2
輸入： s = "bbbbb"
輸出： 1
解釋： 最長為重復的子字符串答案是 "b", 長度為 1.
示例 3
輸入： s = "pwwkew"
輸出： 3
解釋： 最長為重復的子字符串答案是 "wke", 長度為 3.
注意答案必須是自字符串,“pwke” 是一個子列,而不是一個自字符串.
示例 4
輸入： s = ""
輸出： 0
3. 答案
class LongestSubstringWithoutRepeatingCharacters {
func lengthOfLongestSubstring(_ s: String) -> Int {
var maxLen = 0, startIdx = 0, charToPos = [Character: Int]()
let sChars = Array(s)
for (i, char) in sChars.enumerated() {
if let pos = charToPos[char] {
startIdx = max(startIdx, pos)
}
// update to next valid position
charToPos[char] = i + 1
maxLen = max(maxLen, i - startIdx + 1)
}
return maxLen
}
}
- 主要思想：使用字典存儲非重復子字符串的下一個可能有效字符的位置,然后迭代字符串更新 maxLen、dictionary 和遇到重復時的 startIdx .
- 時間復雜度： O(n)
- 空間復雜度： O(n)
點擊前往 LeetCode 練習
該算法題解的 github 倉庫地址是：https://github.com/soapyigu/LeetCode-Swift
