Swift实现LeetCode最小覆盖子串运行超时，如何定位瓶颈并优化？

性能瓶颈 #

• 最核心瓶颈是Swift String的索引偏移操作为O(n)复杂度：Swift的String不属于随机存取集合，每次调用index(_:offsetBy:)获取指定位置字符的操作，时间复杂度和偏移量成正比。你的代码在两层循环中重复执行该操作，1e5长度的字符串会直接将整体时间复杂度拉到O(n²)级别，远高于该算法应有的O(m+n)复杂度。
• 额外开销点1：重复计算字符串长度，while currentEndIndexInt < s.count中的s.count计算复杂度也是O(n)，即使存在系统缓存也会产生不必要的性能损耗。
• 额外开销点2：Character类型字典的高频操作开销，Swift的Character是扩展字素簇类型，哈希计算、查找的开销远高于Java的基础char类型，两层循环中高频读写字典会产生大量额外开销。

优化方案 #

1. 提前将字符串s转为[Character]数组：数组支持O(1)时间的随机下标访问，完全避免索引偏移的额外开销，同时提前将s的长度存入常量，避免重复计算。
2. 替换字典为ASCII数组（LeetCode本题输入均为ASCII字符）：用长度128的整型数组替代[Character:Int]字典，直接用字符的ASCII值作为数组下标，读写操作都是O(1)且无哈希开销，性能提升非常明显。
3. 精简循环内的判断逻辑，减少不必要的可选绑定操作。

优化后代码示例 #

func minWindowSlidingWindow(_ s: String, _ t: String) -> String {
    let sArr = Array(s)
    let sLen = sArr.count
    let tArr = Array(t)
    let tLen = tArr.count
    
    if sLen < tLen { return "" }
    if s == t { return s }
    
    var need = [Int](repeating: 0, count: 128)
    var uniqueRequired = 0
    for c in tArr {
        let ascii = Int(c.asciiValue!)
        if need[ascii] == 0 {
            uniqueRequired += 1
        }
        need[ascii] += 1
    }
    
    var window = [Int](repeating: 0, count: 128)
    var uniqueFormed = 0
    var left = 0
    var minLen = Int.max
    var start = 0
    
    for right in 0..<sLen {
        let c = sArr[right]
        let ascii = Int(c.asciiValue!)
        window[ascii] += 1
        
        if need[ascii] > 0 && window[ascii] == need[ascii] {
            uniqueFormed += 1
        }
        
        while left <= right && uniqueFormed == uniqueRequired {
            let currentLen = right - left + 1
            if currentLen < minLen {
                minLen = currentLen
                start = left
            }
            
            let leftC = sArr[left]
            let leftAscii = Int(leftC.asciiValue!)
            window[leftAscii] -= 1
            if need[leftAscii] > 0 && window[leftAscii] < need[leftAscii] {
                uniqueFormed -= 1
            }
            left += 1
        }
    }
    
    return minLen == Int.max ? "" : String(sArr[start..<start+minLen])
}

内容的提问来源于stack exchange，提问作者Shawn Frank