LeetCode字符串首个唯一字符题解为何同为O(n)却比哈希表方案慢

你对第一版代码的时间复杂度判断有误，两类方案的时间复杂度并不相同：

• 第一版暴力实现的实际时间复杂度为O(n²)：Python内置的s.count()方法底层需要遍历整个字符串统计目标字符出现次数，单次调用的时间开销就是O(n)，叠加外层遍历字符串的n次循环，总操作次数是n²量级，字符串长度较大时耗时会明显升高。
  对应的第一版代码：

class Solution:
    def firstUniqChar(self, s: str) -> int:
        for index, elem in enumerate(s):
            if s.count(elem)==1:
                return index
        return -1

• 第二版哈希表实现的时间复杂度为O(n)：第一次遍历字符串统计字符出现次数的开销是O(n)，第二次遍历哈希表的次数最多为字符集大小（若题目限定输入为小写英文字母，仅最多遍历26次，属于常数级开销），整体为线性时间复杂度，运行速度远高于O(n²)的实现。
  对应的第二版代码：

class Solution:
    def firstUniqChar(self, s: str) -> int:
        hm = {}
        for char in s:
            hm[char] = hm.get(char, 0) + 1
        for key,val in hm.items():
            if val == 1:
                return s.index(key)
        return -1

不存在绝对的「时间复杂度更重要」的结论，需要结合实际运行场景选择：

• 大部分普通开发、算法刷题场景下，内存资源相对充裕，优先优化时间复杂度可以有效提升程序运行效率、符合算法题的时间限制要求，是性价比更高的选择。
• 若运行在嵌入式设备、低功耗物联网终端、超大规模分布式存储等内存资源极度受限的场景中，则需要优先压低空间复杂度，甚至可以牺牲部分时间性能换取空间占用的降低。
  作为算法入门新手，初期可以优先掌握时间复杂度优化的思路，保证代码先通过时间限制，再根据具体需求做空间优化即可。

内容的提问来源于stack exchange，提问作者Yi .D