查找首个非重复字符算法的空间复杂度是否为O(1)

核心结论 #

如果你的算法仅用来处理字符集固定有限的输入（比如仅包含26个小写英文字母的字符串），那么它的空间复杂度确实是O(1)。

具体分析 #

• 你给出的前提是成立的：对于大小固定的字符集（比如26个小写字母），stack和repeats两个列表都只会存储不重复的字符，两者的总长度永远不会超过字符集的总大小，不会随着输入字符串的长度增加而变大，空间占用是固定常量级，完全符合*O(1)*空间复杂度的定义。
• 只有当你的输入没有字符集限制（比如允许任意Unicode字符输入）时，不同字符的数量才可能随着输入规模增长而上升，此时两个列表的最大存储量不再是常量，空间复杂度会变成O(k)（k为输入中出现的不同字符总数），这种场景下就不属于*O(1)*范畴了。

额外补充（可选优化点） #

你当前实现中用到的char in stack、stack.index(char)操作的时间复杂度和列表长度正相关，如果字符集较大，整体时间复杂度会变成O(nk)。如果要优化时间，可以用哈希表（字典）统计每个字符的出现次数，遍历两次字符串即可得到结果，时间复杂度稳定为O(n)，空间复杂度在字符集固定的场景下依然是O(1)。

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