如果你可以使用一点辅助内存,那么你需要的是一小部分比特(用字符的数字代码索引)(如果你的字符是4字节的Unicode字符,你可能想要一个hashmap而不是;-) .从0处的所有位开始:从开始扫描字符串 - 每次,如果与当前字符对应的位已经为1,则发现重复 - 否则,没有重复,将该位设置为1.是O(N).
如果你不能分配任何额外的内存,但可以改变字符串,那么对字符串进行排序然后执行传递以检查相邻的重复项是最好的,O(N log N).
如果您无法分配额外的内存且无法更改字符串,则需要进行O(N平方)检查,检查每个字符与以下所有字符.