[[434992]]

前言

我們社區(qū)從本期開(kāi)始會(huì)將顧毅(Netflix 增長(zhǎng)黑客，《iOS 面試之道》作者，ACE 職業(yè)健身教練。微博:@故胤道長(zhǎng)[1])的 Swift 算法題題解整理為文字版以方便大家學(xué)習(xí)與閱讀。

該算法題解的 github 倉(cāng)庫(kù)地址是：https://github.com/soapyigu/LeetCode-Swift[2]

不積跬步，無(wú)以至千里;不積小流，無(wú)以成江海，Swift社區(qū) 伴你前行。

1. 描述

給定一個(gè)字符串 s ， 找出最長(zhǎng)未重復(fù)的子字符串的長(zhǎng)度。

2. 示例

示例 1

輸入：s = "abcabcbb" 
輸出：3 
解釋?zhuān)鹤铋L(zhǎng)未重復(fù)子字符串答案是"abc"，長(zhǎng)度為 3。 

示例 2

輸入：s = "bbbbb" 
輸出：1 
解釋?zhuān)鹤铋L(zhǎng)未重復(fù)子字符串答案是"b"，長(zhǎng)度為 1。 

示例 3

輸入：s = "pwwkew" 
輸出：1 
解釋?zhuān)鹤铋L(zhǎng)未重復(fù)子字符串答案是"wke"，長(zhǎng)度為 3。注意答案必須是子字符串，“pwke” 是一個(gè)子列，而不是一個(gè)子字符串。 

示例 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 
    } 
} 

主要思想：使用字典存儲(chǔ)非重復(fù)子字符串的下一個(gè)可能有效字符的位置,然后迭代字符串更新 maxLen、dictionary 和遇到重復(fù)時(shí)的 startIdx。

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)