LeetCode字符串首个唯一字符两种解法时间复杂度差异咨询

两者的理论时间复杂度都属于O(n)量级，实际运行速度差主要来自Python的实现特性和题目约束的红利，具体原因如下：

• 内置方法的底层优化加速
  Python的set()、str.count()、str.index()都是底层用C语言实现的原生方法，执行效率远高于纯Python代码写的循环逻辑。哪怕逻辑上完成的是相同的遍历操作，C实现的执行速度比Python解释器跑字节码要快几十到上百倍。
• 字符集约束压缩了上层循环开销
  题目明确限定字符串仅由26个小写英文字母组成，因此set(s)去重后的元素最多只有26个，外层for循环最多执行26次，属于固定常量级开销，完全可以忽略。而你的解法有两层Python级别的全串遍历，每一步的判断、字典操作都是Python层面的字节码执行，累计开销更高。
• 操作层面的额外开销差异
  你的解法中用到了字典做计数，哈希表的查询、赋值虽然是O(1)复杂度，但依然存在Python对象封装、哈希计算、冲突处理的额外开销；而98百分位解法的所有高频运算都在C层完成，几乎没有Python层面的额外开销。

补充说明：从理论时间复杂度推导，你的解法是O(2n)、98百分位解法是O(26*2n)，看起来你的解法复杂度更低，但由于Python的语言特性，这种理论复杂度的差异在n=1e5的量级下，远抵不上C实现带来的速度增益，所以实际运行时98百分位的解法更快。

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