Swift Dictionary性能优化咨询：LeetCode解题超时问题

• 解决LeetCode题目《3. 无重复字符的最长子串》时，Swift版本代码使用Dictionary出现超时（Time Limit Exceeded），无法通过最后一个测试用例，但逻辑完全相同的C代码（使用unordered_map）可以正常通过，原本以为Swift的Dictionary和C的unordered_map是同类型结构。
• 调研发现有资料建议用NSDictionary替代常规Dictionary，但NSDictionary要求使用引用类型，无法直接存储Int或Character等值类型。
• 核心需求：不更换算法逻辑的前提下，实现Swift中字典的高效读写，或者找到性能更优的替代结构（已知该题有更优解法，但重点关注字典相关的性能优化）。

附原超时代码：

func lengthOfLongestSubstring(_ s: String) -> Int {
        var window:[Character:Int] = [:] //swift dictionary is kind of slow?
        let array = Array(s)
        var res = 0
        var left = 0, right = 0
        while right < s.count {
            let rightChar = array[right]
            right += 1
            window[rightChar, default: 0] += 1
            while window[rightChar]! > 1 {
                let leftChar = array[left]
                window[leftChar, default: 0] -= 1
                left += 1
            }
            res = max(res, right - left)
        }
        return res
    }

一、优化Swift Dictionary的使用 #

• 避免强制解包：原代码中window[rightChar]!的强制解包会带来额外性能开销，可改用默认值判断（window[rightChar, default: 0]）替代，同时避免潜在崩溃风险。
• 提前预留容量：Swift的Dictionary动态扩容会损耗性能，初始化时可根据输入字符串长度预设容量，比如var window: [Character: Int] = Dictionary(minimumCapacity: s.count)，减少扩容次数。
• 简化默认值操作：window[rightChar, default: 0] += 1这类操作会隐式触发键值查找与默认值插入，可改为显式判断键是否存在，减少内部逻辑开销：

  if let count = window[rightChar] {
      window[rightChar] = count + 1
  } else {
      window[rightChar] = 1
  }
  

二、性能更优的替代结构 #

• 数组替代字典（字符场景专属）：LeetCode测试用例的字符大多在ASCII范围内，可用数组模拟字典——数组索引对应字符的ASCII值，存储字符最后出现的位置。数组是连续内存访问，缓存友好度远高于字典，读写操作均为O(1)，性能提升明显。
• 放弃NSDictionary：NSDictionary需要将值类型（如Int、Character）包装成NSNumber/NSString，桥接开销反而会降低性能，完全不推荐。

三、优化后的代码示例 #

数组替代字典的高效版本（推荐） #

func lengthOfLongestSubstring(_ s: String) -> Int {
    // 覆盖所有ASCII可打印字符范围
    var lastOccurred = Array(repeating: -1, count: 128)
    let characters = Array(s.utf8)
    var res = 0
    var left = 0
    
    for (right, ascii) in characters.enumerated() {
        let index = Int(ascii)
        // 更新左边界到重复字符的下一位
        left = max(left, lastOccurred[index] + 1)
        // 记录当前字符最新位置
        lastOccurred[index] = right
        // 更新最长子串长度
        res = max(res, right - left + 1)
    }
    return res
}

保持原滑动窗口逻辑的字典优化版 #

func lengthOfLongestSubstring(_ s: String) -> Int {
    // 提前预留容量减少扩容开销
    var window: [Character: Int] = Dictionary(minimumCapacity: s.count)
    let array = Array(s)
    var res = 0
    var left = 0, right = 0
    
    while right < array.count {
        let rightChar = array[right]
        right += 1
        
        // 显式处理键值更新
        if let count = window[rightChar] {
            window[rightChar] = count + 1
        } else {
            window[rightChar] = 1
        }
        
        // 避免强制解包，用默认值判断
        while window[rightChar, default: 0] > 1 {
            let leftChar = array[left]
            if let count = window[leftChar] {
                window[leftChar] = count - 1
            }
            left += 1
        }
        
        res = max(res, right - left)
    }
    return res
}

内容的提问来源于stack exchange，提问作者Steven-Yan